User menu

On the area requirements of Euclidean minimum spanning trees

Bibliographic reference Angelini, P. ; Bruckdorfer, T. ; Chiesa, Marco ; Frati, F. ; Kaufmann, M. ; et. al. On the area requirements of Euclidean minimum spanning trees.WADS (New York, NY, du 15 August 2011 au 17 August 2011).
Permanent URL
  1. Angelini, P., Bruckdorfer, T., Chiesa, M., Frati, F., Kaufmann, M., Squarcella, C.: On the area requirements of Euclidean minimum spanning trees. Technical Report RT-DIA-183-2011, Dept. Comp. Sci. Autom., Roma Tre University (2011)
  2. Arora Sanjeev, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, 10.1145/290179.290180
  3. Bose P., Lenhart W., Liotta G., Characterizing proximity trees, 10.1007/bf02086609
  4. Chan, T.M.: Euclidean bounded-degree spanning tree ratios. Discr. Comp. Geom. 32(2), 177–194 (2004)
  5. Di Giacomo Emilio, Didimo Walter, Liotta Giuseppe, Meijer Henk, Drawing a Tree as a Minimum Spanning Tree Approximation, Algorithms and Computation (2010) ISBN:9783642175138 p.61-72, 10.1007/978-3-642-17514-5_6
  6. Eades P., Whitesides S., The realization problem for Euclidean minimum spanning trees is NP-hard, 10.1007/bf02086608
  7. Francke Andrea, Hoffmann Michael, The Euclidean degree-4 minimum spanning tree problem is NP-hard, 10.1145/1542362.1542399
  8. Frati, F., Kaufmann, M.: Polynomial area bounds for MST embeddings of trees. Tech. Report RT-DIA-122-2008, Dept. of Comp. Sci. Autom., Roma Tre University (2008)
  9. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)
  10. Hurtado, F., Liotta, G., Wood, D.R.: Proximity drawings of high-degree trees. In: CoRR, abs/1008.3193 (2010)
  11. Jothi Raja, Raghavachari Balaji, Degree-bounded minimum spanning trees, 10.1016/j.dam.2008.03.037
  12. Kaufmann Michael, Polynomial Area Bounds for MST Embeddings of Trees, Graph Drawing ISBN:9783540775362 p.88-100, 10.1007/978-3-540-77537-9_12
  13. Liotta, G.: Handbook of Graph Drawing, ch.4. In: Tamassia, R. (ed.). CRC Press, Boca Raton (2011)
  14. Liotta G., Tamassia R., Tollis I. G., Vocca P., Area requirement of Gabriel drawings (extended abstract), Lecture Notes in Computer Science (1997) ISBN:9783540625926 p.135-146, 10.1007/3-540-62592-5_67
  15. Mitchell Joseph S. B., Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, 10.1137/s0097539796309764
  16. Monma Clyde, Suri Subhash, Transitions in geometric minimum spanning trees, 10.1007/bf02293049
  17. Papadimitriou Christos H, Vazirani Umesh V, On two geometric problems related to the travelling salesman problem, 10.1016/0196-6774(84)90029-4