THE REALIZATION PROBLEM FOR EUCLIDEAN MINIMUM SPANNING-TREES IS NP-HARD

Authors
EADES P WHITESIDES S
Citation
P. Eades et S. Whitesides, THE REALIZATION PROBLEM FOR EUCLIDEAN MINIMUM SPANNING-TREES IS NP-HARD, Algorithmica, 16(1), 1996, pp. 60-82
Citations number
24
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
16
Issue
1
Year of publication
1996
Pages
60 - 82
Database
ISI
SICI code
0178-4617(1996)16:1<60:TRPFEM>2.0.ZU;2-E
Abstract
We show that the problem of determining whether a tree can be drawn so that it is the Euclidean minimum spanning tree of the locations of it s vertices is NP-hard.