Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension
DOI10.1137/20M136551XzbMath1504.05277OpenAlexW4307887811MaRDI QIDQ5048290
Laurent Viennot, Guillaume Ducoffe, Michel 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
VC-dimensiondiameterstabbing numbernowhere-dense graph classesproper minor-closed graph classesexact distance oracleradius and eccentricities computations
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Hypergraphs (05C65) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sparsity. Graphs, structures, and algorithms
- Optimal partition trees
- Into the square: on the complexity of some quadratic-time solvable problems
- Multivariate analysis of orthogonal range searching and graph distances
- Algorithms for graphs of bounded treewidth via orthogonal range searching
- The VC dimension of \(k\)-fold union
- Covering planar graphs with a fixed number of balls
- \(\epsilon\)-nets and simplex range queries
- Computation of the center and diameter of outerplanar graphs
- The VC-dimension of set systems defined by graphs
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Diameter and treewidth in minor-closed graph families
- On classes of graphs with strongly sublinear separators
- On limited nondeterminism and the complexity of the V-C dimension
- Quasi-optimal range searching in spaces of finite VC-dimension
- The Vapnik-Chervonenkis dimension of a random graph
- Bounded VC-dimension implies a fractional Helly theorem
- Fast diameter computation within split graphs
- Treewidth of graphs with balanced separations
- VC-dimension and Erdős-Pósa property
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Strongly Sublinear Separators and Polynomial Expansion
- Structural sparsity
- Computing Giant Graph Diameters
- The vectorization of ITPACK 2C
- Spanning trees with low crossing number
- Identifying Codes in Hereditary Classes of Graphs and VC-Dimension
- A simple linear-time algorithm for computing the center of an interval graph
- Three Partition Refinement Algorithms
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- A Separator Theorem for Planar Graphs
- A Separator Theorem for Nonplanar Graphs
- Dually Chordal Graphs
- Product Range Spaces, Sensitive Sampling, and Derandomization
- New Bounds for Approximating Extremal Distances in Undirected Graphs
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter
- Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
- Deciding First-Order Properties of Nowhere Dense Graphs
- Distance labeling in graphs
- Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension
- Planar diameter via metric compression
- Solving linear programs in the current matrix multiplication time
- Towards tight approximation bounds for graph diameter and eccentricities
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Better Approximation Algorithms for the Graph Diameter
- Sparse Distance Preservers and Additive Spanners
- Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time
- Faster shortest-path algorithms for planar graphs
- Diameter determination on restricted graph families
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
