Fast approximation algorithms for the diameter and radius of sparse graphs
From MaRDI portal
Recommendations
- Better approximation algorithms for the graph diameter
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Approximating the Diameter of Planar Graphs in Near Linear Time
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Fast and Simple Approximation of the Diameter and Radius of a Graph
Cited in
(only showing first 100 items - show all)- Formally verified algorithms for upper-bounding state space diameters
- A note on hardness of diameter approximation
- Hardness of RNA folding problem with four symbols
- An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time
- Compact distributed certification of planar graphs
- Fast approximate shortest paths in the congested clique
- Eccentricity queries and beyond using hub labels
- Fast diameter computation within split graphs
- Eccentricity terrain of \(\delta\)-hyperbolic graphs
- Parsimonious formulations for low-diameter clusters
- The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond
- Tight conditional lower bounds for longest common increasing subsequence
- More efficient algorithms for stochastic diameter and some unapproximated problems in metric space
- Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs
- A note on the complexity of computing the number of reachable vertices in a digraph
- A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
- Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings
- Beyond Helly graphs: the diameter problem on absolute retracts
- Distance problems within Helly graphs and \(k\)-Helly graphs
- Computing giant graph diameters
- Linear-time graph distance and diameter approximation
- I/O-efficient hierarchical diameter approximation
- A comparison of three algorithms for approximating the distance distribution in real-world graphs
- Distributed algorithms for network diameter and girth
- Finding the diameter in real-world graphs. Experimentally turning a lower bound into an upper bound
- Faster Approximation of Distances in Graphs
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- New bounds for approximating extremal distances in undirected graphs
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs
- Towards hardness of approximation for polynomial time problems
- Fast approximation of eccentricities and distances in hyperbolic graphs
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy
- Tighter connections between Formula-SAT and shaving logs
- Multivariate analysis of orthogonal range searching and graph distances
- Fine-grained Lower Bounds on Cops and Robbers
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- Fast diameter computation within split graphs
- Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- The Orthogonal Vectors Conjecture for Branching Programs and Formulas
- Fine-Grained Complexity Theory (Tutorial)
- The \(b\)-matching problem in distance-hereditary graphs and beyond
- Algorithms and hardness for diameter in dynamic graphs
- Approximation algorithms for min-distance problems
- Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
- A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
- Tight conditional lower bounds for longest common increasing subsequence
- scientific article; zbMATH DE number 7238981 (Why is no real title available?)
- scientific article; zbMATH DE number 7250154 (Why is no real title available?)
- Orthogonal vectors indexing
- On the hardness of approximate and exact (bichromatic) maximum inner product
- Succinct enumeration of distant vertex pairs
- Towards tight approximation bounds for graph diameter and eccentricities
- Fast and Simple Approximation of the Diameter and Radius of a Graph
- Better approximation algorithms for the graph diameter
- Fast computation of empirically tight bounds for the diameter of massive graphs
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
- scientific article; zbMATH DE number 7650083 (Why is no real title available?)
- Parameterized complexity of diameter
- Approximate proof-labeling schemes
- Parameterized complexity of diameter
- Continuous mean distance of a weighted graph
- Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
- The diameter of AT‐free graphs
- 4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-hard at Time n 4/3
- A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs
- A story of diameter, radius, and (almost) Helly property
- Computing and listing avoidable vertices and paths
- Interpretable random forest model for identification of edge 3-uncolorable cubic graphs
- The energy complexity of diameter and minimum cut computation in bounded-genus networks
- Subquadratic-time algorithm for the diameter and all eccentricities on median graphs
- Maximal distortion of geodesic diameters in polygonal domains
- Computing and listing avoidable vertices and paths
- The energy complexity of diameter and minimum cut computation in bounded-genus networks
- $$\alpha _i$$-Metric Graphs: Radius, Diameter and all Eccentricities
- _i-metric graphs: radius, diameter and all eccentricities
- A new application of orthogonal range searching for computing giant graph diameters
- Parameterized complexity of streaming diameter and connectivity problems
- Determining chromatic index of cubic graph with the use of explainable classifiers: a comparative study
- Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
- On the fine-grained complexity of parity problems
- Hardness of approximate diameter: now for undirected graphs
- Polynomial pass semi-streaming lower bounds for k-cores and degeneracy
- Certificates in P and subquadratic-time computation of radius, diameter, and all eccentricities in graphs
- Approximating the geometric knapsack problem in near-linear time and dynamically
- A VLSI circuit model accounting for wire delay
- Polynomial formulations as a barrier for reduction-based hardness proofs
- The complexity of diameter on H-free graphs
- Parameterized complexity of streaming diameter and connectivity problems
- Obstructions to faster diameter computation: asteroidal sets
- The complexity of diameter on \(H\)-free graphs
- The complexity of non-stationary reinforcement learning
- Inapproximability of diameter in super-linear time: beyond the 5/3 ratio
- Fine-grained hardness for edit distance to a fixed sequence
- Optimal fine-grained hardness of approximation of linear equations
- 4 vs 7 sparse undirected unweighted diameter is SETH-hard at time \(n^{4/3}\)
- Approximation algorithms for min-distance problems in DAGs
This page was built for publication: Fast approximation algorithms for the diameter and radius of sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495822)
