The Inverse Voronoi Problem in Graphs II: Trees

被引：2

作者：

Bonnet, Edouard ^{[1
]}

Cabello, Sergio ^{[2
,5
]}

Mohar, Bojan ^{[3
]}

Perez-Roses, Hebert ^{[4
]}

机构：

[1] Univ Claude Bernard Lyon 1, Univ Lyon, ENS Lyon, CNRS,LIP UMR, Lyon, France

[2] Univ Ljubljana, Fac Math & Phys, Ljubljana, Slovenia

[3] Simon Fraser Univ, Dept Math, Burnaby, BC, Canada

[4] Univ Rovira & Virgili, Dept Engn Informat & Matemat, Tarragona, Spain

[5] IMFM, Ljubljana, Slovenia

来源：

ALGORITHMICA | 2021年 / 83卷 / 05期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Voronoi diagram in graphs; Inverse Voronoi problem; Trees; Applications of binary search trees; Dynamic programming in trees; Lower bounds;

D O I：

10.1007/s00453-020-00774-8

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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 + Sigma(U is an element of U) vertical bar U vertical bar is the size of the description of the input. We also provide a lower bound of Omega(n log n) time for trees with n vertices.

引用

页码：1165 / 1200

页数：36

共 50 条

[1] The Inverse Voronoi Problem in Graphs II: Trees
Édouard Bonnet
Sergio Cabello
Bojan Mohar
Hebert Pérez-Rosés
Algorithmica, 2021, 83 : 1165 - 1200
[2] The Inverse Voronoi Problem in Graphs I: Hardness
Édouard Bonnet
Sergio Cabello
Bojan Mohar
Hebert Pérez-Rosés
Algorithmica, 2020, 82 : 3018 - 3040
[3] The Inverse Voronoi Problem in Graphs I: Hardness
Bonnet, Edouard
Cabello, Sergio
Mohar, Bojan
Perez-Roses, Hebert
ALGORITHMICA, 2020, 82 (10) : 3018 - 3040
[4] The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample
Barrett, Wayne
Hall, H. Tracy
Loewy, Raphael
LINEAR ALGEBRA AND ITS APPLICATIONS, 2009, 431 (08) : 1147 - 1191
[5] Boundary spectral inverse problem on a class of graphs (trees) by the BC method
Belishev, MI
INVERSE PROBLEMS, 2004, 20 (03) : 647 - 672
[6] The weighted farthest color Voronoi diagram on trees and graphs
Hurtado, F
Klein, R
Langetepe, E
Sacristán, V
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2004, 27 (01): : 13 - 26
[7] INVERSE PROBLEMS FOR QUANTUM TREES II: RECOVERING MATCHING CONDITIONS FOR STAR GRAPHS
Avdonin, Sergei
Kurasov, Pavel
Nowaczyk, Marlena
INVERSE PROBLEMS AND IMAGING, 2010, 4 (04) : 579 - 598
[8] THE COMBINATORIAL INVERSE EIGENVALUE PROBLEM II: ALL CASES FOR SMALL GRAPHS
Barrett, Wayne
Nelson, Curtis
Sinkovic, John
Yang, Tianyi
ELECTRONIC JOURNAL OF LINEAR ALGEBRA, 2014, 27 : 742 - 778
[9] Inverse booking problem: Inverse chromatic number problem in interval graphs
Chung, Yerim
Culus, Jean-Francois
Demange, Marc
WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2008, 4921 : 180 - +
[10] ON AN EDGE RANKING PROBLEM OF TREES AND GRAPHS
IYER, AV
RATLIFF, HD
VIJAYAN, G
DISCRETE APPLIED MATHEMATICS, 1991, 30 (01) : 43 - 52

← 1 2 3 4 5 →