Approximation algorithms for min-distance problems in DAGs

DOI10.4230/LIPICS.ICALP.2021.60MaRDI QIDQ7241158zbMATH OpenFDO

Authors M. Dalirrooyfard, Jenny Kaufmann

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.60

zbMATH Keywords

diametereccentricitiesfine-grained complexitygraph algorithmsradius

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A new algorithm for optimal 2-constraint satisfaction and its implications
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• All-pairs shortest paths for unweighted undirected graphs in o(mn) time
• Approximating the diameter of planar graphs in near linear time
• Approximation algorithms for min-distance problems
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Better approximation algorithms for the graph diameter
• Diameter determination on restricted graph families
• Efficient algorithms for center problems in cactus networks
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Fast sparse matrix multiplication
• Faster Approximation of Distances in Graphs
• Fine-grained complexity for sparse graphs
• scientific article; zbMATH DE number 4137792 (Why is no real title available?)
• scientific article; zbMATH DE number 1305501 (Why is no real title available?)
• scientific article; zbMATH DE number 2086613 (Why is no real title available?)
• scientific article; zbMATH DE number 2119672 (Why is no real title available?)
• scientific article; zbMATH DE number 2119682 (Why is no real title available?)
• If the current clique algorithms are optimal, so is Valiant's parser
• Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
• Networks cannot compute their diameter in sublinear time
• On the complexity of k-SAT
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
• Subcubic equivalences between graph centrality problems, APSP and diameter
• Subcubic equivalences between path, matrix, and triangle problems
• Subgraph Isomorphism in Planar Graphs and Related Problems
• The absolute center of a network
• The complexity of satisfiability of small depth circuits

Cited in

(1)

• Shortest paths in multimode graphs

This page was built for publication: Approximation algorithms for min-distance problems in DAGs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241158)