Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
From MaRDI portal
Publication:4575605
Recommendations
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Approximating maximum diameter-bounded subgraphs
- Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
- Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
- Approximating maximum diameter-bounded subgraph in unit disk graphs
- Approximating maximum diameter-bounded subgraph in unit disk graphs
- Sublinear-time algorithms for approximating graph parameters
- Towards tight approximation bounds for graph diameter and eccentricities
- Better approximation algorithms for the graph diameter
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
Cited in
(64)- Computing graph distances parameterized by treewidth and diameter
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Improved distance queries and cycle counting by Frobenius normal form
- scientific article; zbMATH DE number 7559218 (Why is no real title available?)
- Towards tight approximation bounds for graph diameter and eccentricities
- scientific article; zbMATH DE number 7561539 (Why is no real title available?)
- Rectilinear link diameter and radius in a rectilinear polygonal domain
- Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
- Eccentricity terrain of \(\delta\)-hyperbolic graphs
- scientific article; zbMATH DE number 7053319 (Why is no real title available?)
- Multivariate analysis of orthogonal range searching and graph distances
- Approximating all-points furthest pairs and maximum spanning trees in metric spaces
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Tighter connections between Formula-SAT and shaving logs
- Diameter, eccentricities and distance oracle computations on \(H\)-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- When can graph hyperbolicity be computed in linear time?
- An efficient noisy binary search in graphs via Median approximation
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Subquadratic-time algorithm for the diameter and all eccentricities on median graphs
- scientific article; zbMATH DE number 7650079 (Why is no real title available?)
- Scheduling lower bounds via AND subset sum
- \( \alpha_i\)-metric graphs: radius, diameter and all eccentricities
- A story of diameter, radius, and (almost) Helly property
- The Orthogonal Vectors Conjecture for Branching Programs and Formulas
- Continuous mean distance of a weighted graph
- Orthogonal vectors indexing
- Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
- The diameter of AT‐free graphs
- Parameterized complexity of streaming diameter and connectivity problems
- Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
- Formally verified algorithms for upper-bounding state space diameters
- scientific article; zbMATH DE number 7561506 (Why is no real title available?)
- Maximum matching in almost linear time on graphs of bounded clique-width
- A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
- A note on the complexity of computing the number of reachable vertices in a digraph
- Towards hardness of approximation for polynomial time problems
- Fast approximation of eccentricities and distances in hyperbolic graphs
- On the power of tree-depth for fully polynomial FPT algorithms
- Eccentricity queries and beyond using hub labels
- Parameterized complexity of diameter
- Computing giant graph diameters
- Parameterized analysis and crossing minimization problems
- A linear-time parameterized algorithm for computing the width of a DAG
- Beyond Helly graphs: the diameter problem on absolute retracts
- Minimum Cuts in Surface Graphs
- Distance problems within Helly graphs and \(k\)-Helly graphs
- Fast diameter computation within split graphs
- Multivariate analysis of orthogonal range searching and graph distances
- The complexity of finding (approximate sized) distance-\(d\) dominating set in tournaments
- Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
- Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy
- $$\alpha _i$$-Metric Graphs: Radius, Diameter and all Eccentricities
- Tight conditional lower bounds for vertex connectivity problems
- Computation of diameter, radius and center of permutation graphs
- Towards sub-quadratic diameter computation in geometric intersection graphs
- Graphs with \(G^p\)-connected medians
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- On adaptive algorithms for maximum matching
- Optimal centrality computations within bounded clique-width graphs
- The fine-grained complexity of multi-dimensional ordering properties
- Medians in median graphs and their cube complexes in linear time
This page was built for publication: Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575605)
