Listing Subgraphs by Cartesian Decomposition

Abstract : We investigate a decomposition technique for listing problems in graphs and set systems. It is based on the Cartesian product of some iterators, which list the solutions of simpler problems. Our ideas applies to several problems, and we illustrate one of them in depth, namely, listing all minimum spanning trees of a weighted graph G. Here iterators over the spanning trees for unweighted graphs can be obtained by a suitable modification of the listing algorithm by [Shioura et al., SICOMP 1997], and the decomposition of G is obtained by suitably partitioning its edges according to their weights. By combining these iterators in a Cartesian product scheme that employs Gray coding, we give the first algorithm which lists all minimum spanning trees of G in constant delay, where the delay is the time elapsed between any two consecutive outputs. Our solution requires polynomial preprocessing time and uses polynomial space.
Document type :
Conference papers
Liste complète des métadonnées

https://hal.inria.fr/hal-01964703
Contributor : Marie-France Sagot <>
Submitted on : Sunday, December 23, 2018 - 11:55:07 AM
Last modification on : Tuesday, February 26, 2019 - 10:54:02 AM
Document(s) archivé(s) le : Sunday, March 24, 2019 - 1:21:02 PM

File

LIPIcs-MFCS-2018-84.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi, Luca Versari. Listing Subgraphs by Cartesian Decomposition. MFCS 2018 - International Symposium on Mathematical Foundations of Computer Science, Aug 2018, Liverpool, United Kingdom. pp.1868-8969, ⟨10.4230/LIPIcs.MFCS.2018.84⟩. ⟨hal-01964703⟩

Share

Metrics

Record views

15

Files downloads

142