Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
DOI10.1137/20M136551XzbMATH Open1504.05277OpenAlexW4307887811MaRDI QIDQ5048290FDOQ5048290
Authors: Guillaume Ducoffe, Laurent Viennot, M. A. Habib 
Publication date: 15 November 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/20m136551x
Recommendations
- Computing graph distances parameterized by treewidth and diameter
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Better approximation algorithms for the graph diameter
- The diameter of AT‐free graphs
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
diameterVC-dimensionstabbing numbernowhere-dense graph classesproper minor-closed graph classesexact distance oracleradius and eccentricities computations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Analysis of algorithms (68W40) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62) Hypergraphs (05C65) Graph minors (05C83)
Cites Work
- Graph theory
- The vectorization of ITPACK 2C
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- Distance labeling in graphs
- \(\epsilon\)-nets and simplex range queries
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Diameter determination on restricted graph families
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Three Partition Refinement Algorithms
- A Separator Theorem for Planar Graphs
- A Separator Theorem for Nonplanar Graphs
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- Sparsity. Graphs, structures, and algorithms
- Dually Chordal Graphs
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- On limited nondeterminism and the complexity of the V-C dimension
- Title not available (Why is that?)
- Diameter and treewidth in minor-closed graph families
- Bounded VC-dimension implies a fractional Helly theorem
- Faster shortest-path algorithms for planar graphs
- The VC-dimension of set systems defined by graphs
- The Vapnik-Chervonenkis dimension of a random graph
- Title not available (Why is that?)
- Algorithms for graphs of bounded treewidth via orthogonal range searching
- Optimal partition trees
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- The VC dimension of \(k\)-fold union
- Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications
- Quasi-optimal range searching in spaces of finite VC-dimension
- Spanning trees with low crossing number
- A simple linear-time algorithm for computing the center of an interval graph
- Title not available (Why is that?)
- Structural sparsity
- Identifying codes in hereditary classes of graphs and VC-dimension
- Computation of the center and diameter of outerplanar graphs
- Product Range Spaces, Sensitive Sampling, and Derandomization
- Into the square: on the complexity of some quadratic-time solvable problems
- Covering planar graphs with a fixed number of balls
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Multivariate analysis of orthogonal range searching and graph distances
- VC-dimension and Erdős-Pósa property
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
- Better tradeoffs for exact distance oracles in planar graphs
- Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
- Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension
- New bounds for approximating extremal distances in undirected graphs
- Solving linear programs in the current matrix multiplication time
- Treewidth of graphs with balanced separations
- On the hardness of partially dynamic graph problems and connections to diameter
- Better approximation algorithms for the graph diameter
- Strongly sublinear separators and polynomial expansion
- Sparse Distance Preservers and Additive Spanners
- Approximation algorithms for polynomial-expansion and low-density graphs
- On classes of graphs with strongly sublinear separators
- Towards tight approximation bounds for graph diameter and eccentricities
- Planar diameter via metric compression
- Fast diameter computation within split graphs
- Computing giant graph diameters
- Title not available (Why is that?)
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
Cited In (8)
- Multivariate analysis of orthogonal range searching and graph distances
- Sample Compression Schemes for Balls in Graphs
- Subquadratic-time algorithm for the diameter and all eccentricities on median graphs
- VC-dimension and Erdős-Pósa property
- A story of diameter, radius, and (almost) Helly property
- Fast diameter computation within split graphs
- Multivariate analysis of orthogonal range searching and graph distances
- Towards sub-quadratic diameter computation in geometric intersection graphs
This page was built for publication: Diameter, eccentricities and distance oracle computations on \(H\)-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5048290)
