research-article

The Euclidean degree-4 minimum spanning tree problem is NP-hard

Authors:

Andrea Francke,

Michael HoffmannAuthors Info & Claims

SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometry

Pages 179 - 188

https://doi.org/10.1145/1542362.1542399

Published: 08 June 2009 Publication History

Abstract

We show that it is an NP-hard problem to decide for a given set P of n points in the Euclidean plane and a given parameter k∈R, whether P admits a spanning tree of maximum vertex degree four whose sum of edge lengths does not exceed k.

References

[1]

S. Arora. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In Proc. 37th Annu. IEEE Sympos. Found. Comput. Sci., pages 2--11, 1996.

Digital Library

[2]

S. Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM, 45(5):753--782, 1998.

Digital Library

[3]

S. Arora and K. Chang. Approximation schemes for degree-restricted MST and red-blue separation problems. Algorithmica, 40(3):189--210, 2004.

[4]

T. M. Chan. Euclidean bounded--degree spanning tree ratios. Discrete Comput. Geom., 32(2):177--194, 2004.

Digital Library

[5]

E. D. Demaine, J. S. B. Mitchell, and J. O'Rourke. The Open Problems Project. http://maven.smith.edu/~orourke/TOPP/.

[6]

S. P. Fekete. Problem 48: Bounded-degree minimum Euclidean spanning tree. http://maven.smith.edu/~orourke/TOPP/P48.html.

[7]

S. P. Fekete, S. Khuller, M. Klemmstein, B. Raghavachari, and N. Young. A network--flow technique for finding low-weight bounded-degree spanning trees. J. Algorithms, 24(2):310--324, 1997.

Digital Library

[8]

M. R. Garey and D. S. Johnson. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math., 32:826--834, 1977.

Digital Library

[9]

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, NY, 1979.

Digital Library

[10]

R. Jothi and B. Raghavachari. Degree-bounded minimum spanning trees. Discrete Appl. Math., 157(5):960--970, 2009.

Digital Library

[11]

S. Khuller, B. Raghavachari, and N. Young. Low-degree spanning trees of small weight. SIAM J. Comput., 25(2):355--368, 1996.

Digital Library

[12]

J. S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput., 28:1298--1309, 1999.

Digital Library

[13]

C. Monma and S. Suri. Transitions in geometric minimum spanning trees. Discrete Comput. Geom., 8(3):265--293, 1992.

Digital Library

[14]

C. H. Papadimitriou. The Euclidean traveling salesman problem is NP-complete. Theoret. Comput. Sci., 4:237--244, 1977.

[15]

C. H. Papadimitriou and U. V. Vazirani. On two geometric problems related to the travelling salesman problem. J. Algorithms, 5:231--246, 1984.

[16]

A. Papakostas and I. G. Tollis. Algorithms for area-efficient orthogonal drawings. Comput. Geom. Theory Appl., 9(1-2):83--110, 1998.

Digital Library

[17]

G. Robins and J. S. Salowe. Low-degree minimum spanning trees. Discrete Comput. Geom., 14(2):151--165, 1995.

Digital Library

[18]

R. Tamassia and I. G. Tollis. Planar grid embedding in linear time. IEEE Trans. Circuits Syst., CAS-36(9):1230--1234, 1989.

Cited By

Biniaz A(2021)Euclidean Bottleneck Bounded-Degree Spanning Tree RatiosDiscrete & Computational Geometry10.1007/s00454-021-00286-4Online publication date: 16-Apr-2021
https://doi.org/10.1007/s00454-021-00286-4
Andersen PRas C(2019)Algorithms for Euclidean Degree Bounded Spanning Tree ProblemsInternational Journal of Computational Geometry & Applications10.1142/S021819591950003129:02(121-160)Online publication date: 20-Sep-2019
https://doi.org/10.1142/S0218195919500031
Andersen PRas C(2019)Degree bounded bottleneck spanning trees in three dimensionsJournal of Combinatorial Optimization10.1007/s10878-019-00490-2Online publication date: 29-Nov-2019
https://doi.org/10.1007/s10878-019-00490-2
Show More Cited By

Index Terms

The Euclidean degree-4 minimum spanning tree problem is NP-hard
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Trees
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Degree-bounded minimum spanning trees

Given n points in the Euclidean plane, the degree-@d minimum spanning tree (MST) problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most @d. The problem is NP-hard for 2@__ __@d@__ __3, while the NP-hardness of ...
Minimum spanning tree cycle intersection problem on outerplanar graphs
Abstract
We study the minimum spanning tree cycle intersection (MSTCI) problem on outerplanar graphs in this paper. Consider a connected simple graph G = ( V , E ) and any spanning tree T = ( V , E T ) of G, it is well-known that each non-tree edge e ∈ E ∖...
Variations of the maximum leaf spanning tree problem for bipartite graphs

The maximum leaf spanning tree problem is known to be NP-complete. In [M.S. Rahman, M. Kaykobad, Complexities of some interesting problems on spanning trees, Inform. Process. Lett. 94 (2005) 93-97], a variation on this problem was posed. This variation ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometry

June 2009

426 pages

ISBN:9781605585017

DOI:10.1145/1542362

Program Chairs:
John Hershberger
Mentor Graphics Corp.
,
Efi Fogel
Tel Aviv University

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 June 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SoCG '09

Sponsor:

SoCG '09: 25th Annual Symposium on Computational Geometry

June 8 - 10, 2009

Aarhus, Denmark

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
381
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Biniaz A(2021)Euclidean Bottleneck Bounded-Degree Spanning Tree RatiosDiscrete & Computational Geometry10.1007/s00454-021-00286-4Online publication date: 16-Apr-2021
https://doi.org/10.1007/s00454-021-00286-4
Andersen PRas C(2019)Algorithms for Euclidean Degree Bounded Spanning Tree ProblemsInternational Journal of Computational Geometry & Applications10.1142/S021819591950003129:02(121-160)Online publication date: 20-Sep-2019
https://doi.org/10.1142/S0218195919500031
Andersen PRas C(2019)Degree bounded bottleneck spanning trees in three dimensionsJournal of Combinatorial Optimization10.1007/s10878-019-00490-2Online publication date: 29-Nov-2019
https://doi.org/10.1007/s10878-019-00490-2
Andersen PRas C(2016)Minimum bottleneck spanning trees with degree boundsNetworks10.1002/net.2171068:4(302-314)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1002/net.21710
Angelini PBruckdorfer TChiesa MFrati FKaufmann MSquarcella C(2014)On the area requirements of Euclidean minimum spanning treesComputational Geometry: Theory and Applications10.1016/j.comgeo.2012.10.01147:2(200-213)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1016/j.comgeo.2012.10.011
Dobrev SKranakis EPonce OPlžík M(2012)Robust Sensor Range for Constructing Strongly Connected Spanning Digraphs in UDGsComputer Science – Theory and Applications10.1007/978-3-642-30642-6_12(112-124)Online publication date: 2012
https://doi.org/10.1007/978-3-642-30642-6_12
Angelini PBruckdorfer TChiesa MFrati FKaufmann MSquarcella C(2011)On the area requirements of Euclidean minimum spanning treesProceedings of the 12th international conference on Algorithms and data structures10.5555/2033190.2033193(25-36)Online publication date: 15-Aug-2011
https://dl.acm.org/doi/10.5555/2033190.2033193
Frati FKaufmann M(2011)Polynomial area bounds for MST embeddings of treesComputational Geometry: Theory and Applications10.1016/j.comgeo.2011.05.00544:9(529-543)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1016/j.comgeo.2011.05.005
Angelini PBruckdorfer TChiesa MFrati FKaufmann MSquarcella C(2011)On the Area Requirements of Euclidean Minimum Spanning TreesAlgorithms and Data Structures10.1007/978-3-642-22300-6_3(25-36)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22300-6_3
Dobrev SKranakis EKrizanc DOpatrny JPonce OStacho L(2010)Strong connectivity in sensor networks with given number of directional antennae of bounded angleProceedings of the 4th international conference on Combinatorial optimization and applications - Volume Part II10.5555/1940424.1940430(72-86)Online publication date: 18-Dec-2010
https://dl.acm.org/doi/10.5555/1940424.1940430
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents