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

DOI10.1137/1.9781611975994.117OpenAlexW3002826123MaRDI QIDQ5146902FDOQ5146902

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

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)