Document Open Access Logo

Listing Subgraphs by Cartesian Decomposition

Authors Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi, Luca Versari

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.84.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Author Details

Alessio Conte
  • National Institute of Informatics, Tokyo, Japan
Roberto Grossi
  • Dipartimento di Informatica, Università di Pisa, Pisa, Italy
Andrea Marino
  • Dipartimento di Informatica, Università di Pisa, Pisa, Italy
Romeo Rizzi
  • Dipartimento di Informatica, Università di Verona, Verona, Italy
Luca Versari
  • Dipartimento di Informatica, Università di Pisa, Pisa, Italy

Funding

This work has been partially supported by MIUR (Italian Ministry of University and Research) and JST CREST, Grant Number JPMJCR1401, Japan

Cite As Get BibTex

Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi, and Luca Versari. Listing Subgraphs by Cartesian Decomposition. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 84:1-84:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.84

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Graph algorithms
  • listing
  • minimum spanning trees
  • constant delay

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. David Avis and Komei Fukuda. Reverse search for enumeration. Discrete Applied Mathematics, 65(1-3):21-46, 1996. Google Scholar
  2. Manu Basavaraju, Pinar Heggernes, Pim van 't Hof, Reza Saei, and Yngve Villanger. Maximal induced matchings in triangle-free graphs. Journal of Graph Theory, 83(3):231-250, 2016. URL: http://dx.doi.org/10.1002/jgt.21994.
  3. Cüneyt F Bazlamaçcı and Khalil S Hindi. Minimum-weight spanning tree algorithms a survey and empirical study. Computers &Operations Research, 28(8):767-785, 2001. Google Scholar
  4. Etienne Birmelé, Rui Ferreira, Roberto Grossi, Andrea Marino, Nadia Pisanti, Romeo Rizzi, and Gustavo Sacomoto. Optimal listing of cycles and st-paths in undirected graphs. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1884-1896. SIAM, 2013. Google Scholar
  5. Coenraad Bron and Joep Kerbosch. Finding all cliques of an undirected graph (algorithm 457). Communications of the ACM, 16(9):575-576, 1973. Google Scholar
  6. Alessio Conte, Roberto Grossi, Andrea Marino, and Romeo Rizzi. Listing acyclic orientations of graphs with single and multiple sources. In LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings, pages 319-333, 2016. URL: http://dx.doi.org/10.1007/978-3-662-49529-2_24.
  7. Alessio Conte, Roberto Grossi, Andrea Marino, Takeaki Uno, and Luca Versari. Listing maximal independent sets with minimal space and bounded delay. In String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Palermo, Italy, September 26-29, 2017, Proceedings, pages 144-160, 2017. URL: http://dx.doi.org/10.1007/978-3-319-67428-5_13.
  8. Alessio Conte, Mamadou Moustapha Kanté, Yota Otachi, Takeaki Uno, and Kunihiro Wasa. Efficient enumeration of maximal k-degenerate subgraphs in a chordal graph. In Yixin Cao and Jianer Chen, editors, Computing and Combinatorics, pages 150-161, Cham, 2017. Springer International Publishing. Google Scholar
  9. Alessio Conte, Kazuhiro Kurita, Kunihiro Wasa, and Takeaki Uno. Listing acyclic subgraphs and subgraphs of bounded girth in directed graphs. In Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part II, pages 169-181, 2017. URL: http://dx.doi.org/10.1007/978-3-319-71147-8_12.
  10. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms, third edition, 2009. Google Scholar
  11. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  12. David Eppstein. Representing all minimum spanning trees with applications to counting and generation. Information and Computer Science, University of California, Irvine, 1995. Google Scholar
  13. Ira M. Gessel. Enumerative applications of a decomposition for graphs and digraphs. Discrete Mathematics, 139(1):257-271, 1995. URL: http://dx.doi.org/10.1016/0012-365X(94)00135-6.
  14. Ronald L Graham and Pavol Hell. On the history of the minimum spanning tree problem. Annals of the History of Computing, 7(1):43-57, 1985. Google Scholar
  15. David S Johnson, Mihalis Yannakakis, and Christos H Papadimitriou. On generating all maximal independent sets. Information Processing Letters, 27(3):119-123, 1988. Google Scholar
  16. Sanjiv Kapoor and Hariharan Ramesh. Algorithms for enumerating all spanning trees of undirected and weighted graphs. SIAM Journal on Computing, 24(2):247-265, 1995. Google Scholar
  17. Donald E Knuth. The art of computer programming, volume 4, fascicle 2: Generating all tuples and permutations, 2005. Google Scholar
  18. Joseph B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1):48-50, 1956. URL: http://www.jstor.org/stable/2033241.
  19. Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, and Takeaki Uno. Efficient enumeration of dominating sets for sparse graphs. CoRR, abs/1802.07863, 2018. URL: http://arxiv.org/abs/1802.07863.
  20. F. Maffioli. Complexity of optimum undirected tree problems: a survey of recent results. In Analysis and design of algorithms in combinatorial optimization, pages 107-128. Springer, 1981. Google Scholar
  21. Kazuhisa Makino and Takeaki Uno. New algorithms for enumerating all maximal cliques. In Algorithm Theory - SWAT 2004, pages 260-272, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. Google Scholar
  22. Tomomi Matsui. An algorithm for finding all the spanning trees in undirected graphs. METR93-08, Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo, 16:237-252, 1993. Google Scholar
  23. Tomomi Matsui. A flexible algorithm for generating all the spanning trees in undirected graphs. Algorithmica, 18(4):530-543, 1997. Google Scholar
  24. Matúš Mihalák, Przemysław Uznański, and Pencho Yordanov. Prime factorization of the kirchhoff polynomial: Compact enumeration of arborescences. In 2016 Proceedings of the Thirteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pages 93-105. SIAM, 2016. Google Scholar
  25. Reinhard Pichler, Stefan Rümmele, and Stefan Woltran. Counting and enumeration problems with bounded treewidth. In International Conference on Logic for Programming Artificial Intelligence and Reasoning, pages 387-404. Springer, 2010. Google Scholar
  26. A. R. Pierce. Bibliography on algorithms for shortest path, shortest spanning tree, and related circuit routing problems (1956-1974). Networks, 5(2):129-149, 1975. Google Scholar
  27. Ronald C Read and Robert E Tarjan. Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks, 5(3):237-252, 1975. Google Scholar
  28. Benno Schwikowski and Ewald Speckenmeyer. On enumerating all minimal solutions of feedback problems. Discrete Applied Mathematics, 117(1-3):253-265, 2002. URL: http://dx.doi.org/10.1016/S0166-218X(00)00339-5.
  29. Akiyoshi Shioura, Akihisa Tamura, and Takeaki Uno. An optimal algorithm for scanning all spanning trees of undirected graphs. SIAM Journal on Computing, 26(3):678-692, 1997. Google Scholar
  30. Kenneth Sörensen and Gerrit K Janssens. An algorithm to generate all spanning trees of a graph in order of increasing cost. Pesquisa Operacional, 25(2):219-229, 2005. Google Scholar
  31. Robert E. Tarjan. Decomposition by clique separators. Discrete Mathematics, 55(2):221-232, 1985. URL: http://dx.doi.org/10.1016/0012-365X(85)90051-2.
  32. Takeaki Uno. Two general methods to reduce delay and change of enumeration algorithms, 2003. NII Technical Report NII-2003-004E, Tokyo, Japan. Google Scholar
  33. Kunihiro Wasa and Takeaki Uno. Efficient enumeration of bipartite subgraphs in graphs. CoRR, abs/1803.03839, 2018. URL: http://arxiv.org/abs/1803.03839.
  34. Perrin Wright. Counting and constructing minimal spanning trees. Bulletin of the Institute of Combinatorics and its Applications, 21:65-76, 1997. Google Scholar
  35. Takeo Yamada, Seiji Kataoka, and Kohtaro Watanabe. Listing all the minimum spanning trees in an undirected graph. International Journal of Computer Mathematics, 87(14):3175-3185, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact