License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.84
URN: urn:nbn:de:0030-drops-96666
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9666/
Go to the corresponding LIPIcs Volume Portal

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

Listing Subgraphs by Cartesian Decomposition

pdf-format:
LIPIcs-MFCS-2018-84.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{conte_et_al:LIPIcs:2018:9666,
  author =	{Alessio Conte and Roberto Grossi and Andrea Marino and Romeo Rizzi and Luca Versari},
  title =	{{Listing Subgraphs by Cartesian Decomposition}},
  booktitle =	{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)},
  pages =	{84:1--84:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9666},
  URN =		{urn:nbn:de:0030-drops-96666},
  doi =		{10.4230/LIPIcs.MFCS.2018.84},
  annote =	{Keywords: Graph algorithms, listing, minimum spanning trees, constant delay}
}

Keywords: Graph algorithms, listing, minimum spanning trees, constant delay
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI