Efficient Algorithms for Listing k Disjoint st-Paths in Graphs

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.
Type de document :
Communication dans un congrès
LATIN 2018 - 13th Latin American Symposium on Theoretical Informatics, Apr 2018, Buenos Aires, Argentina. 10807, pp.544-557, 2018, Lecture Notes in Computer Science. 〈10.1007/978-3-319-77404-6_40〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01964712
Contributeur : Marie-France Sagot <>
Soumis le : dimanche 23 décembre 2018 - 12:29:45
Dernière modification le : jeudi 7 février 2019 - 15:36:53

Fichier

paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Roberto Grossi, Andrea Marino, Luca 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. 10807, pp.544-557, 2018, Lecture Notes in Computer Science. 〈10.1007/978-3-319-77404-6_40〉. 〈hal-01964712〉

Partager

Métriques

Consultations de la notice

7

Téléchargements de fichiers

82