Going beyond surfaces in diameter approximation
From MaRDI portal
Cites work
- k -apices of Minor-closed Graph Classes. II. Parameterized Algorithms
- A near-optimal planarization algorithm
- A tight VC-dimension analysis of clustering coresets with applications
- Almost optimal exact distance oracles for planar graphs
- Almost-linear ε -emulators for planar graphs
- Approximate distance oracles for planar graphs with subpolynomial error dependency
- Approximate shortest paths and distance oracles in weighted unit-disk graphs
- Approximate tree decompositions of planar graphs in linear time
- Approximating the Diameter of Planar Graphs in Near Linear Time
- Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Better diameter algorithms for bounded VC-dimension graphs and geometric intersection graphs
- Better tradeoffs for exact distance oracles in planar graphs
- Bounding -scatter dimension via metric sparsity
- Compact oracles for reachability and approximate distances in planar digraphs
- Computing diameter+2 in truly-subquadratic time for unit-disk graphs
- Computing graph distances parameterized by treewidth and diameter
- Coresets for clustering in excluded-minor graphs and beyond
- Covering planar graphs with a fixed number of balls
- Covering planar metrics (and beyond): O(1) trees suffice
- Diameter and treewidth in minor-closed graph families
- Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems
- Equivalence of local treewidth and linear local treewidth and its algorithmic applications
- Excluded minors, network decomposition, and multicommodity flow
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Faster Approximate Diameter and Distance Oracles in Planar Graphs
- Finding geometric representations of apex graphs is \textsf{NP}-hard
- Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
- Graph minors. XVI: Excluding a non-planar graph
- scientific article; zbMATH DE number 7788598 (Why is no real title available?)
- Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
- Low treewidth embeddings of planar and minor-free metrics
- Minor containment and disjoint paths in almost-linear time
- Object location using path separators
- On the density of families of sets
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Optimal approximate distance oracle for planar graphs
- Planar and minor-free metrics embed into metrics of polylogarithmic treewidth with expected multiplicative distortion arbitrarily close to 1
- Planar diameter via metric compression
- Shortcut partitions in minor-free graphs: Steiner point removal, distance oracles, tree covers, and more
- Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
- Sparse covers for planar graphs and graphs that exclude a fixed minor
- Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
- Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more
- The max-cut problem on graphs not contractible to \(K_ 5\)
- VC set systems in minor-free (di)graphs and applications
- VC-dimension and Erdős-Pósa property
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
- What else can Voronoi diagrams do for diameter in planar graphs?
This page was built for publication: Going beyond surfaces in diameter approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7322433)
