Covering planar graphs with a fixed number of balls

DOI10.1007/S00454-006-1260-0MaRDI QIDQ878065zbMATH OpenOpenAlexFDO

Authors Victor Chepoi, Bertrand Estellon, Yann Vaxès

Publication date 26 April 2007

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00454-006-1260-0

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Covering nearly surface-embedded graphs with a fixed number of balls
• On covering bridged plane triangulations with balls
• Largest planar graphs of diameter two and fixed maximum degree
• Domination in planar graphs with small diameter II.
• Covering planar graphs with forests

Cited in

(20)

• Packing and covering balls in graphs excluding a minor
• Packing and covering with balls on Busemann surfaces
• VC-dimension and Erdős-Pósa property
• Kernelization and approximation of distance-r independent sets on nowhere dense graphs
• Approximating maximum diameter-bounded subgraph in unit disk graphs
• Beyond Helly graphs: the diameter problem on absolute retracts
• On covering bridged plane triangulations with balls
• Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• On the VC-dimension‎, ‎covering and separating properties of the cycle and spanning tree hypergraphs of graphs
• Approximating maximum diameter-bounded subgraph in unit disk graphs
• The degree/diameter problem in maximal planar bipartite graphs
• The degree/diameter problem in maximal planar bipartite graphs
• Sample Compression Schemes for Balls in Graphs
• A story of diameter, radius, and (almost) Helly property
• Computing diameter+2 in truly-subquadratic time for unit-disk graphs
• Obstructions to faster diameter computation: asteroidal sets
• Better diameter algorithms for bounded VC-dimension graphs and geometric intersection graphs
• Going beyond surfaces in diameter approximation
• Covering nearly surface-embedded graphs with a fixed number of balls
• Problems from CGCS Luminy, May 2007

This page was built for publication: Covering planar graphs with a fixed number of balls

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