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 条

[41] Boundary controllability and inverse problem for the wave equation on graphs
Avdonin, S.
Nurtazina, K.
Sheronova, T.
PROCEEDINGS OF 2006 MEDITERRANEAN CONFERENCE ON CONTROL AND AUTOMATION, VOLS 1 AND 2, 2006, : 61 - +
[42] THE COMBINATORIAL INVERSE EIGENVALUE PROBLEM: COMPLETE GRAPHS AND SMALL GRAPHS WITH STRICT INEQUALITY
Barrett, Wayne
Lazenby, Anne
Malloy, Nicole
Nelson, Curtis
Sexton, William
Smith, Ryan
Sinkovic, John
Yang, Tianyi
ELECTRONIC JOURNAL OF LINEAR ALGEBRA, 2013, 26 : 656 - 672
[43] VORONOI TREES AND CLUSTERING PROBLEMS
DEHNE, F
NOLTEMEIER, H
INFORMATION SYSTEMS, 1987, 12 (02) : 171 - 175
[44] The Inverse Problem on Subset Sums, II
Wu, Jian-Dong
JOURNAL OF INTEGER SEQUENCES, 2013, 16 (08)
[45] ON AN INVERSE PROBLEM TO FROBENIUS' THEOREM II
Meng, Wei
Shi, Jiangtao
Chen, Kelin
JOURNAL OF ALGEBRA AND ITS APPLICATIONS, 2012, 11 (05)
[46] Voronoi games on cycle graphs
Mavronicolas, Marios
Monien, Burkhard
Papadopoulou, Vicky G.
Schoppmann, Florian
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2008, PROCEEDINGS, 2008, 5162 : 503 - +
[47] The optimal cost chromatic partition problem for trees and interval graphs
Kroon, LG
Sen, A
Deng, HY
Roy, A
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 1997, 1197 : 279 - 292
[48] Discrete Integral and Discrete Derivative on Graphs and Switch Problem of Trees
Khalifeh, M. H.
Esfahanian, Abdol-Hossein
MATHEMATICS, 2023, 11 (07)
[49] The inverse inertia problem for the complements of partial k-trees
van der Holst, Hein
LINEAR ALGEBRA AND ITS APPLICATIONS, 2013, 439 (07) : 2167 - 2175
[50] QUANTUM COMPUTING ALGORITHMS FOR INVERSE PROBLEMS ON GRAPHS AND AN NP-COMPLETE INVERSE PROBLEM
Ilmavirta, Joonas
Lassas, Matti
Lu, Jinpeng
Oksanen, Lauri
Ylinen, Lauri
arXiv, 2023,

← 1 2 3 4 5 →