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 条

[21] The inverse center subtree problem on tree graphs
Nguyen, Kien Trung
Nguyen-Thu, Huong
Luan, Nguyen Thanh
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2025,
[22] Inverse Harary Index Problem for Chain Graphs
Hanif, Shahistha
ENGINEERING LETTERS, 2024, 32 (04) : 812 - 817
[23] On the Inverse Problem for Quantum Graphs with One Cycle
Kurasov, P.
ACTA PHYSICA POLONICA A, 2009, 116 (05) : 765 - 771
[24] A structured inverse spectrum problem for infinite graphs
Monfared, Keivan Hassani
Khanmohammadi, Ehssan
LINEAR ALGEBRA AND ITS APPLICATIONS, 2018, 539 : 28 - 43
[25] The relativistic inverse scattering problem for quantum graphs
Sabirov, K. K.
Sobirov, Z. A.
Karpova, O. V.
Saidov, A. A.
NANOSYSTEMS-PHYSICS CHEMISTRY MATHEMATICS, 2015, 6 (02): : 192 - 197
[26] An inverse problem for differential pencils on graphs with a cycle
Yurko, Vjacheslav A.
JOURNAL OF INVERSE AND ILL-POSED PROBLEMS, 2014, 22 (05): : 625 - 641
[27] A Calderon type inverse problem for tree graphs
Gernandt, Hannes
Rohleder, Jonathan
LINEAR ALGEBRA AND ITS APPLICATIONS, 2022, 646 : 29 - 42
[28] A partial inverse problem for quantum graphs with a loop
Guan, Sheng-Yu
Yang, Chuan-Fu
Wu, Dong-Jie
JOURNAL OF INVERSE AND ILL-POSED PROBLEMS, 2021, 29 (04): : 577 - 585
[29] Symmetries of quantum graphs and the inverse scattering problem
Boman, J
Kurasov, P
ADVANCES IN APPLIED MATHEMATICS, 2005, 35 (01) : 58 - 70
[30] Voronoi drawings of trees
Liotta, G
Meijer, H
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2003, 24 (03): : 147 - 178

← 1 2 3 4 5 →