Counting Approximately-Shortest Paths in Directed Acyclic Graphs

Matús Mihalák; Rastislav Šrámek; Peter Widmayer

doi:10.1007/978-3-319-08001-7_14

Counting Approximately-Shortest Paths in Directed Acyclic Graphs

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

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceeding › Academic › peer-review

Abstract

Given a directed acyclic graph with positive edge-weights, two vertices s and t, and a threshold-weight l, we present a fully-polynomial time approximation-scheme for the problem of counting the s-t paths of length at most l. We extend the algorithm for the case of two (or more) instances of the same problem. That is, given two graphs that have the same vertices and edges and differ only in edge-weights, and given two threshold-weights l 1 and l 2, we show how to approximately count the s-t paths that have length at most l 1 in the first graph and length not much larger than l 2 in the second graph. We believe that our algorithms should find application in counting approximate solutions of related optimization problems, where finding an (optimum) solution can be reduced to the computation of a shortest path in a purpose-built auxiliary graph.

Original language	English
Title of host publication	Proc. 11th International Workshop on Approximation and Online Algorithms (WAOA)
Publisher	Springer Verlag
Pages	156-167
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-319-08001-7_14
Publication status	Published - 2013
Externally published	Yes

Publication series

Series	Lecture Notes in Computer Science
Volume	8447

Access to Document

10.1007/978-3-319-08001-7_14

Cite this

@inproceedings{bfcf5affb4344fdd9d8c57098a42a033,

title = "Counting Approximately-Shortest Paths in Directed Acyclic Graphs",

abstract = "Given a directed acyclic graph with positive edge-weights, two vertices s and t, and a threshold-weight l, we present a fully-polynomial time approximation-scheme for the problem of counting the s-t paths of length at most l. We extend the algorithm for the case of two (or more) instances of the same problem. That is, given two graphs that have the same vertices and edges and differ only in edge-weights, and given two threshold-weights l 1 and l 2, we show how to approximately count the s-t paths that have length at most l 1 in the first graph and length not much larger than l 2 in the second graph. We believe that our algorithms should find application in counting approximate solutions of related optimization problems, where finding an (optimum) solution can be reduced to the computation of a shortest path in a purpose-built auxiliary graph.",

author = "Mat{\'u}s Mihal{\'a}k and Rastislav {\v S}r{\'a}mek and Peter Widmayer",

year = "2013",

doi = "10.1007/978-3-319-08001-7_14",

language = "English",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "156--167",

booktitle = "Proc. 11th International Workshop on Approximation and Online Algorithms (WAOA)",

address = "Germany",

}

Counting Approximately-Shortest Paths in Directed Acyclic Graphs. / Mihalák, Matús; Šrámek, Rastislav; Widmayer, Peter.
Proc. 11th International Workshop on Approximation and Online Algorithms (WAOA). Springer Verlag, 2013. p. 156-167 (Lecture Notes in Computer Science, Vol. 8447).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceeding › Academic › peer-review

TY - GEN

T1 - Counting Approximately-Shortest Paths in Directed Acyclic Graphs

AU - Mihalák, Matús

AU - Šrámek, Rastislav

AU - Widmayer, Peter

PY - 2013

Y1 - 2013

N2 - Given a directed acyclic graph with positive edge-weights, two vertices s and t, and a threshold-weight l, we present a fully-polynomial time approximation-scheme for the problem of counting the s-t paths of length at most l. We extend the algorithm for the case of two (or more) instances of the same problem. That is, given two graphs that have the same vertices and edges and differ only in edge-weights, and given two threshold-weights l 1 and l 2, we show how to approximately count the s-t paths that have length at most l 1 in the first graph and length not much larger than l 2 in the second graph. We believe that our algorithms should find application in counting approximate solutions of related optimization problems, where finding an (optimum) solution can be reduced to the computation of a shortest path in a purpose-built auxiliary graph.

AB - Given a directed acyclic graph with positive edge-weights, two vertices s and t, and a threshold-weight l, we present a fully-polynomial time approximation-scheme for the problem of counting the s-t paths of length at most l. We extend the algorithm for the case of two (or more) instances of the same problem. That is, given two graphs that have the same vertices and edges and differ only in edge-weights, and given two threshold-weights l 1 and l 2, we show how to approximately count the s-t paths that have length at most l 1 in the first graph and length not much larger than l 2 in the second graph. We believe that our algorithms should find application in counting approximate solutions of related optimization problems, where finding an (optimum) solution can be reduced to the computation of a shortest path in a purpose-built auxiliary graph.

U2 - 10.1007/978-3-319-08001-7_14

DO - 10.1007/978-3-319-08001-7_14

M3 - Conference article in proceeding

T3 - Lecture Notes in Computer Science

SP - 156

EP - 167

BT - Proc. 11th International Workshop on Approximation and Online Algorithms (WAOA)

PB - Springer Verlag

ER -