Counting Approximately-Shortest Paths in Directed Acyclic Graphs

DOI10.1007/978-3-319-08001-7_14zbMath1331.05212arXiv1304.6707OpenAlexW1814265121MaRDI QIDQ3188874

Rastislav Šrámek, Matúš Mihalák, Peter Widmayer

Publication date: 2 September 2014

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1304.6707

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Probability estimation via policy restrictions, convexification, and approximate sampling