Fast estimation of diameter and shortest paths (without matrix multiplication)

No abstract is available for this paper.

• Publication year

  1996

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  1996-01-28

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/S0097539796303421
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• All pairs almost shortest paths

  1996cited by this paper
• Introduction to algorithms

  1996cited by this paper
• On Diameter Verification and Boolean Matrix Multiplication.

  1995cited by this paper
• Polylog-time and near-linear work approximation scheme for undirected shortest paths

  1994cited by this paper
• The Stanford GraphBase - a platform for combinatorial computing

  1993influential reference
• Fast algorithms for constructing t-spanners and paths with stretch t

  1993cited by this paper
• Near-linear cost sequential and distributed constructions of sparse neighborhood covers

  1993cited by this paper
• Witnesses for Boolean matrix multiplication and for shortest paths

  1992cited by this paper
• On the all-pairs-shortest-path problem

  1992cited by this paper
• On the Exponent of the All Pairs Shortest Path Problem

  1991cited by this paper
• Clique partitions, graph compression and speeding-up algorithms

  1991cited by this paper
• Matrix multiplication via arithmetic progressions

  1987cited by this paper
• Random Graphs

  1985cited by this paper
• On the ratio of optimal integral and fractional covers

  1975cited by this paper
• Approximation algorithms for combinatorial problems

  1973cited by this paper
• Gaussian elimination is not optimal

  1969influential reference

• Constrained graph generation: Preserving diameter and clustering coefficient simultaneously

  2026cites this paper
• Quantum algorithms and lower bounds for eccentricity, radius, and diameter in undirected graphs

  2025influential citation
• Spanning and Metric Tree Covers Parameterized by Treewidth

  2025cites this paper
• Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms

  2025cites this paper
• Improved Additive Approximation Algorithms for APSP

  2025influential citation
• Improved 2-Approximate Shortest Paths for close vertex pairs

  2025influential citation
• Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension

  2025cites this paper
• Beyond 2-Approximation for k-Center in Graphs

  2025cites this paper
• Simple Approximations for General Spanner Problems

  2025cites this paper
• Approximating Optimal Labelings for Temporal Connectivity

  2025cites this paper
• New algorithms for girth and cycle detection

  2025cites this paper
• Connectivity Labeling in Faulty Colored Graphs

  2024cites this paper
• Additive Spanner Lower Bounds with Optimal Inner Graph Structure

  2024cites this paper
• Faster Combinatorial k-Clique Algorithms

  2024cites this paper
• Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs

  2024cites this paper
• A Sublinear Algorithm for Approximate Shortest Paths in Large Networks

  2024cites this paper
• New weighted additive spanners

  2024cites this paper
• Lightweight Near-Additive Spanners

  2024cites this paper
• Path-Reporting Distance Oracles with Near-Logarithmic Stretch and Linear Size

  2023cites this paper
• Almost-Optimal Sublinear Additive Spanners

  2023cites this paper
• Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n)

  2023cites this paper
• New Additive Emulators

  2023cites this paper
• Multi-Task Processing in Vertex-Centric Graph Systems: Evaluations and Insights

  2023cites this paper
• New Algorithms for All Pairs Approximate Shortest Paths

  2023influential citation
• propagate: A Seed Propagation Framework to Compute Distance-Based Metrics on Very Large Graphs

  2023cites this paper
• Approximating Min-Diameter: Standard and Bichromatic

  2023cites this paper
• A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs

  2023cites this paper
• Fast 2-Approximate All-Pairs Shortest Paths

  2023cites this paper
• Multi-Priority Graph Sparsification

  2023cites this paper
• Computing Distance-based metrics on Very Large Graphs

  2023cites this paper
• Dynamic algorithms for k-center on graphs

  2023cites this paper
• Simple Linear-Size Additive Emulators

  2023cites this paper
• Fault-Tolerant ST-Diameter Oracles

  2023cites this paper
• Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation

  2023cites this paper
• New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms

  2023influential citation
• On Problems Related to Unbounded SubsetSum: A Unified Combinatorial Approach

  2022cites this paper
• Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs

  2022cites this paper
• Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets

  2022cites this paper
• Bridge Girth: A Unifying Notion in Network Design

  2022cites this paper
• New Lower Bounds and Upper Bounds for Listing Avoidable Vertices

  2022cites this paper
• Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond

  2022cites this paper
• New Additive Spanner Lower Bounds by an Unlayered Obstacle Product

  2022cites this paper
• Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates

  2022cites this paper
• Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles

  2022influential citation
• All-Pairs Shortest Path Distances with Differential Privacy: Improved Algorithms for Bounded and Unbounded Weights

  2022cites this paper
• On Scalable Computation of Graph Eccentricities

  2022cites this paper
• New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths

  2022cites this paper
• New Additive Approximations for Shortest Paths and Cycles

  2022influential citation
• Practicably Boosting the Processing Performance of BFS-like Algorithms on Semi-External Graph System via I/O-Efficient Graph Ordering

  2022cites this paper
• Sparsification lower bound for linear spanners in directed graphs

  2021cites this paper
• Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product

  2021cites this paper
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities

  2021cites this paper
• Vertex Fault-Tolerant Emulators

  2021cites this paper
• A Unified Approach for All Pairs Approximate Shortest Paths in Weighted Undirected Graphs

  2021cites this paper
• 4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-hard at Time n4/3

  2021cites this paper
• Additive Sparsification of CSPs

  2021cites this paper
• All-Pairs Shortest Paths for Real-Weighted Undirected Graphs with Small Additive Error

  2021cites this paper
• Fast Construction of 4-Additive Spanners

  2021cites this paper
• Hardness of Approximate Diameter: Now for Undirected Graphs

  2021cites this paper
• Approximation Algorithms for Min-Distance Problems in DAGs

  2021cites this paper
• Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths

  2021influential citation
• Percolation centrality via Rademacher Complexity

  2021cites this paper
• Weighted Sparse and Lightweight Spanners with Local Additive Error

  2021cites this paper
• Parameter tuning of a genetic algorithm for finding central vertices in graphs

  2021cites this paper
• Multi-level Weighted Additive Spanners

  2021cites this paper
• On Additive Spanners in Weighted Graphs with Local Error

  2021cites this paper
• Multi-level Weighted Additive Spanners ∗

  2021cites this paper
• Approximating Min-Mean-Cycle for low-diameter graphs in near-optimal time and memory

  2020cites this paper
• A Fast Algorithm for Source-Wise Round-Trip Spanners

  2020cites this paper
• Distributed Network Design

  2020cites this paper
• Multi-objective trajectory optimization in planning for sequential activities across space and through time

  2020cites this paper
• Efficient Estimation of Graph Trussness

  2020cites this paper
• Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms

  2020cites this paper
• Near-Additive Spanners and Near-Exact Hopsets, A Unified View

  2020cites this paper
• Some General Structure for Extremal Sparsification Problems

  2020cites this paper
• New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners

  2020cites this paper
• Improved weighted additive spanners

  2020cites this paper
• Weighted Additive Spanners

  2020influential citation
• New (α, β) Spanners and Hopsets

  2020cites this paper
• Tight conditional lower bounds for approximating diameter in directed graphs

  2020cites this paper
• Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio

  2020cites this paper
• Computing Plan-Length Bounds Using Lengths of Longest Paths

  2020cites this paper
• Fault Tolerant Approximate BFS Structures with Additive Stretch

  2020cites this paper
• Distributed Exact Shortest Paths in Sublinear Time

  2020cites this paper
• Settling SETH vs. approximate sparse directed unweighted diameter (up to (NU)NSETH)

  2020cites this paper
• A note on distance-preserving graph sparsification

  2020cites this paper
• Improved SETH-hardness of unweighted Diameter

  2020cites this paper
• Subcubic Equivalences Between Graph Centrality Measures and Complementary Problems

  2019cites this paper
• An FPT Algorithm for Minimum Additive Spanner Problem

  2019cites this paper
• Distributed Construction of Light Networks

  2019cites this paper
• Equality of opportunity and integration in social networks

  2019cites this paper
• Plan-Length Bounds: Beyond 1-Way Dependency

  2019cites this paper
• New Bounds for Combinatorial Problems and Quasi-Gray Codes

  2019cites this paper
• Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time

  2019cites this paper
• Graph Spanners: A Tutorial Review

  2019cites this paper
• Small Stretch Pairwise Spanners and D-spanners A Thesis Submitted to the Tata Institute of Fundamental Research, Mumbai for the degree of Master of Sciences in Computer Science by

  2019cites this paper
• Estimating the Percolation Centrality of Large Networks through Pseudo-dimension Theory

  2019cites this paper
• Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems

  2019influential citation
• Fast approximation of eccentricities and distances in hyperbolic graphs

  2019cites this paper
• New $(\alpha,\beta)$ Spanners and Hopsets

  2019cites this paper