Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs

DOI10.1137/1.9781611974331.ch28zbMath1410.68392OpenAlexW4243936346MaRDI QIDQ4575605

Amir Abboud, Joshua Wang, Virginia Vassilevska Williams

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974331.ch28

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Approximation algorithms (68W25)

Related Items (55)

Medians in median graphs and their cube complexes in linear time ⋮ Scheduling lower bounds via AND subset sum ⋮ Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Minimum Cuts in Surface Graphs ⋮ Rectilinear link diameter and radius in a rectilinear polygonal domain ⋮ Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ A note on the complexity of computing the number of reachable vertices in a digraph ⋮ Eccentricity queries and beyond using hub labels ⋮ Formally verified algorithms for upper-bounding state space diameters ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ A faster diameter problem algorithm for a chordal graph, with a connection to its center problem ⋮ Parameterized analysis and crossing minimization problems ⋮ On the Power of Tree-Depth for Fully Polynomial FPT Algorithms ⋮ A linear-time parameterized algorithm for computing the width of a DAG ⋮ Beyond Helly graphs: the diameter problem on absolute retracts ⋮ Eccentricity terrain of \(\delta\)-hyperbolic graphs ⋮ Continuous mean distance of a weighted graph ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ The diameter of AT‐free graphs ⋮ Unnamed Item ⋮ A story of diameter, radius, and (almost) Helly property ⋮ Computation of diameter, radius and center of permutation graphs ⋮ Distance problems within Helly graphs and \(k\)-Helly graphs ⋮ Graphs with \(G^p\)-connected medians ⋮ Subquadratic-time algorithm for the diameter and all eccentricities on median graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Complexity of Finding (Approximate Sized) Distance-d Dominating Set in Tournaments ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized aspects of triangle enumeration ⋮ Parameterized approximation algorithms for some location problems in graphs ⋮ When can graph hyperbolicity be computed in linear time? ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Parameterized complexity of diameter ⋮ Computing Giant Graph Diameters ⋮ 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 ⋮ The Orthogonal Vectors Conjecture for Branching Programs and Formulas ⋮ Unnamed Item ⋮ Improved distance queries and cycle counting by Frobenius normal form ⋮ Multivariate analysis of orthogonal range searching and graph distances ⋮ The fine-grained complexity of multi-dimensional ordering properties ⋮ Optimal centrality computations within bounded clique-width graphs ⋮ Maximum matching in almost linear time on graphs of bounded clique-width ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time ⋮ Unnamed Item ⋮ Fast Diameter Computation within Split Graphs ⋮ An efficient noisy binary search in graphs via Median approximation

This page was built for publication: Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs