Approximately counting approximately-shortest paths in directed acyclic graphs

DOI10.1007/s00224-014-9571-7zbMath1332.05073OpenAlexW2064257849MaRDI QIDQ260255

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

Publication date: 21 March 2016

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-014-9571-7

zbMATH Keywords

countingshortest pathsapproximation algorithms

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Paths and cycles (05C38) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Related Items

Faster FPTASes for counting and random generation of knapsack solutions, The Complexity of Aggregates over Extractions by Regular Expressions, On modelling and solving the shortest path problem with evidential weights, Robust optimization in the presence of uncertainty: a generic approach, Unnamed Item

Cites Work

• The complexity of computing the permanent
• A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions
• Robust optimization in the presence of uncertainty
• The Complexity of Enumeration and Reliability Problems
• Biological Sequence Analysis
• A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem
• Counting Minimum Weight Spanning Trees
• Reducibility among Combinatorial Problems
• An FPTAS for #Knapsack and Related Counting Problems
• Unnamed Item
• Unnamed Item