Abstract:
We prove that the Davenport–Mahler bound holds for arbitrary graphs with vertices on the set of roots of a given univariate polynomial with complex coefficients. © 2016 Elsevier Inc.
Referencias:
- Basu, S., Pollack, R., Roy, M.-F., Algorithms in Real Algebraic Geometry (2006) Algorithms and Computation in Mathematics, 10. , second ed. Springer-Verlag Berlin
- Davenport, J., Cylindrical algebraic decomposition. Technical Report 88-10 (1988), University of Bath England; Du, Z., Sharma, V., Yap, C., Amortized bound for root isolation via Sturm sequences (2007) Symbolic-numeric Computation, Trends Math., pp. 113-129. , Birkhäuser Basel
- Eigenwillig, A., Real Root Isolation for Exact and Approximate Polynomials Using Descartes’ Rule of Signs (2008), (Doctoral dissertation) Universität des Saarlandes; Eigenwillig, A., Sharma, V., Yap, C., Almost tight recursion tree bounds for the Descartes method (2006) ISSAC 2006, pp. 71-78. , ACM New York
- Emiris, I., Mourrain, B., Tsigaridas, E., The DMM bound: multivariate (aggregate) separation bounds (2010) ISSAC 2010, pp. 243-250. , ACM New York
- Johnson, J., Algorithms for polynomial real root isolation (1998) Quantifier elimination and cylindrical algebraic decomposition, Linz, 1993, Texts Monogr. Symbol. Comput., pp. 269-299. , Springer Vienna
- Kerber, M., Sagraloff, M., A worst-case bound for topology computation of algebraic curves (2012) J. Symbolic Comput., 47 (3), pp. 239-258
- Kincaid, D., Cheney, W., Numerical analysis (1996) Mathematics of Scientific Computing, , second ed. Brooks/Cole Publishing Co. Pacific Grove, CA
- Mahler, K., An inequality for the discriminant of a polynomial (1964) Michigan Math. J., 11, pp. 257-262
- Mignotte, M., Ştefănescu, D., (1999) Polynomials. An Algorithmic Approach, Springer Series in Discrete Mathematics and Theoretical Computer Science, , Springer-Verlag Singapore Singapore Centre for Discrete Mathematics & Theoretical Computer Science, Auckland
- Yap, C., Fundamental Problems of Algorithmic Algebra (2000), Oxford University Press New York
Citas:
---------- APA ----------
Escorcielo, P. & Perrucci, D.
(2017)
. On the Davenport–Mahler bound. Journal of Complexity, 41, 72-81.
http://dx.doi.org/10.1016/j.jco.2016.12.001---------- CHICAGO ----------
Escorcielo, P., Perrucci, D.
"On the Davenport–Mahler bound"
. Journal of Complexity 41
(2017) : 72-81.
http://dx.doi.org/10.1016/j.jco.2016.12.001---------- MLA ----------
Escorcielo, P., Perrucci, D.
"On the Davenport–Mahler bound"
. Journal of Complexity, vol. 41, 2017, pp. 72-81.
http://dx.doi.org/10.1016/j.jco.2016.12.001---------- VANCOUVER ----------
Escorcielo, P., Perrucci, D. On the Davenport–Mahler bound. J. Complexity. 2017;41:72-81.
http://dx.doi.org/10.1016/j.jco.2016.12.001