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

DOI10.1137/1.9781611974331.CH28zbMATH Open1410.68392OpenAlexW4243936346MaRDI QIDQ4575605FDOQ4575605

Authors: 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

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

Mathematics Subject Classification ID

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

Cited In (64)

Improved distance queries and cycle counting by Frobenius normal form
Towards tight approximation bounds for graph diameter and eccentricities
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Multivariate analysis of orthogonal range searching and graph distances
Eccentricity terrain of $\delta$-hyperbolic graphs
Rectilinear link diameter and radius in a rectilinear polygonal domain
Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
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
When can graph hyperbolicity be computed in linear time?
Diameter, eccentricities and distance oracle computations on $H$-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
An efficient noisy binary search in graphs via Median approximation
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
Title not available (Why is that?)
A story of diameter, radius, and (almost) Helly property
Scheduling lower bounds via AND subset sum
The Orthogonal Vectors Conjecture for Branching Programs and Formulas
Orthogonal vectors indexing
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
The diameter of AT‐free graphs
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
Title not available (Why is that?)
Formally verified algorithms for upper-bounding state space diameters
A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
Maximum matching in almost linear time on graphs of bounded clique-width
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
Computing giant graph diameters
Parameterized analysis and crossing minimization problems
Minimum Cuts in Surface Graphs
A linear-time parameterized algorithm for computing the width of a DAG
Beyond Helly graphs: the diameter problem on absolute retracts
Fast diameter computation within split graphs
The complexity of finding (approximate sized) distance-$d$ dominating set in tournaments
Distance problems within Helly graphs and $k$-Helly graphs
Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy
Multivariate analysis of orthogonal range searching and graph distances
On adaptive algorithms for maximum matching
Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
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
Computing graph distances parameterized by treewidth and diameter
Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
Approximating all-points furthest pairs and maximum spanning trees in metric spaces
Subquadratic-time algorithm for the diameter and all eccentricities on median graphs
$ \alpha_i$-metric graphs: radius, diameter and all eccentricities
Continuous mean distance of a weighted graph
Parameterized complexity of streaming diameter and connectivity problems
Parameterized complexity of diameter
Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
$$\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

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)