Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension

DOI10.1137/1.9781611975994.117MaRDI QIDQ5146902zbMATH OpenOpenAlexFDO

Authors Guillaume Ducoffe, Laurent Viennot, M. A. Habib

Publication date 2 February 2021

Published in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(13)

• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• \( \alpha_i\)-metric graphs: radius, diameter and all eccentricities
• Packing and covering balls in graphs excluding a minor
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Fast diameter computation within split graphs
• Parameterized complexity of streaming diameter and connectivity problems
• Distance problems within Helly graphs and \(k\)-Helly graphs
• Beyond Helly graphs: the diameter problem on absolute retracts
• Diameter, eccentricities and distance oracle computations on \(H\)-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• A story of diameter, radius, and (almost) Helly property
• The diameter of AT‐free graphs
• Eccentricity queries and beyond using hub labels
• Parameterized complexity of diameter

This page was built for publication: Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension

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