Efficient Algorithms for Listing k Disjoint st-Paths in Graphs - Archive ouverte HAL Access content directly
Conference Papers Year : 2018

## Efficient Algorithms for Listing k Disjoint st-Paths in Graphs

(1, 2) , (1, 2) , (1)
1
2
Roberto P Grossi
• Function : Author
• PersonId : 857937
Luca P Versari
• Function : Author
• PersonId : 991831

#### Abstract

Given a connected graph G of m edges and n vertices, we consider the basic problem of listing all the choices of k vertex-disjoint st-paths, for any two input vertices s, t of G and a positive integer k. Our algorithm takes O(m) time per solution, using O(m) space and requiring O(F k (G)) setup time, where $F k (G) = O(m min{k, n 2/3 log n, √ m log n})$ is the cost of running a max-flow algorithm on G to compute a flow of size k. The proposed techniques are simple and apply to other related listing problems discussed in the paper.

#### Domains

Computer Science [cs]

### Dates and versions

hal-01964712 , version 1 (23-12-2018)

### Identifiers

• HAL Id : hal-01964712 , version 1
• DOI :

### Cite

Roberto P Grossi, Andrea Marino, Luca P Versari. Efficient Algorithms for Listing k Disjoint st-Paths in Graphs. LATIN 2018 - 13th Latin American Symposium on Theoretical Informatics, Apr 2018, Buenos Aires, Argentina. pp.544-557, ⟨10.1007/978-3-319-77404-6_40⟩. ⟨hal-01964712⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

12 View