Algorithmica, 2021-05, Vol.83 (5), p.1165-1200
2021
Volltextzugriff (PDF)
Details
- Autor(en) / Beteiligte
- Titel
- The Inverse Voronoi Problem in Graphs II: Trees
- Ist Teil von
- Algorithmica, 2021-05, Vol.83 (5), p.1165-1200
- Ort / Verlag
- New York: Springer US
- Erscheinungsjahr
- 2021
- Quelle
- Alma/SFX Local Collection
- Beschreibungen/Notizen
- We consider the inverse Voronoi diagram problem in trees: given a tree T with positive edge-lengths and a collection U of subsets of vertices of V ( T ), decide whether U is a Voronoi diagram in T with respect to the shortest-path metric. We show that the problem can be solved in O ( N + n log 2 n ) time, where n is the number of vertices in T and N = n + ∑ U ∈ U | U | is the size of the description of the input. We also provide a lower bound of Ω ( n log n ) time for trees with n vertices.
- Sprache
- Englisch
- Identifikatoren
- ISSN: 0178-4617eISSN: 1432-0541DOI: 10.1007/s00453-020-00774-8Titel-ID: cdi_proquest_journals_2510297288
- Format
- –
- Schlagworte
- Algorithm Analysis and Problem Complexity, Algorithms, Apexes, Computer Science, Computer Systems Organization and Communication Networks, Data Structures and Information Theory, Graph theory, Lower bounds, Mathematics of Computing, Shortest-path problems, Theory of Computation, Trees (mathematics), Voronoi graphs