Sökning: onr:"swepub:oai:DiVA.org:kth-222332" >
On the area require...
On the area requirements of Euclidean minimum spanning trees
-
Angelini, P. (författare)
-
Bruckdorfer, T. (författare)
-
- Chiesa, Marco, 1987- (författare)
- Roma Tre University, Italy
-
visa fler...
-
Frati, F. (författare)
-
Kaufmann, M. (författare)
-
Squarcella, C. (författare)
-
visa färre...
-
(creator_code:org_t)
- Elsevier, 2014
- 2014
- Engelska.
-
Ingår i: Computational geometry. - : Elsevier. - 0925-7721 .- 1879-081X. ; 47:2, s. 200-213
- Relaterad länk:
-
https://doi.org/10.1...
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- In their seminal paper on Euclidean minimum spanning trees, Monma and Suri (1992) proved that any tree of maximum degree 5 admits a planar embedding as a Euclidean minimum spanning tree. Their algorithm constructs embeddings with exponential area; however, the authors conjectured that there exist n-vertex trees of maximum degree 5 that require c(n) x c(n) area to be embedded as Euclidean minimum spanning trees, for some constant c > 1. In this paper, we prove the first exponential lower bound on the area requirements for embedding trees as Euclidean minimum spanning trees.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Euclidean minimum spanning tree
- Minimum area
- Lower bound
- Computational geometry
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas