The inverse Voronoi problem in graphs. II: Trees

DOI10.1007/S00453-020-00774-8MaRDI QIDQ2663704zbMATH OpenOpenAlexFDO

Authors Édouard Bonnet, S. Cabello, Bojan Mohar, Hebert Pérez-Rosés

Publication date 19 April 2021

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.12547

zbMATH Keywords

applications of binary search treesdynamic programming in treesinverse Voronoi problemlower boundstreesVoronoi diagram in graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The inverse Voronoi problem in graphs. I: Hardness
• Voronoi drawings of trees
• scientific article; zbMATH DE number 1542607
• The weighted farthest color Voronoi diagram on trees and graphs.
• An \(\mathcal{O}(n \log n)\) algorithm for the inverse 1-median problem on trees with variable vertex weights and edge reductions

Cites work

• Advanced Data Structures
• Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
• scientific article; zbMATH DE number 4211552 (Why is no real title available?)
• Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
• Self-adjusting binary search trees
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• The inverse Voronoi problem in graphs. I: Hardness

Cited in

(6)

• The inverse Voronoi problem in graphs. I: Hardness
• Minimum consistent subset problem for trees
• On selecting a fraction of leaves with disjoint neighborhoods in a plane tree
• Inverse problems on graphs: recovering the tree of strings by the BC-method
• Minimum consistent subset of simple graph classes
• Balancing graph Voronoi diagrams with one more vertex

This page was built for publication: The inverse Voronoi problem in graphs. II: Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2663704)