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 http://hdl.handle.net/2078.1/178581
  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