×

ToTo: an open database for computation, storage and retrieval of tree decompositions. (English) Zbl 1358.05002

Summary: Many NP-hard problems on graphs become tractable on graphs of low treewidth, but the corresponding algorithms require access to a tree decomposition of the graph of low (ideally, minimum) width. Unfortunately computation of treewidth is itself NP-hard and a wide variety of exact, heuristic and approximation algorithms have been proposed for this problem. To support this ongoing research we present here ToTo, an open graph database for computation, storage and rapid retrieval of tree decompositions. We hope that the database will become both a central repository for important graphs and benchmark datasets and extend the use of treewidth beyond the usual communities: the database and associated algorithms can be accessed via a web browser and do not require installation of any specialist software.

MSC:

05-04 Software, source code, etc. for problems pertaining to combinatorics
05C85 Graph algorithms (graph-theoretic aspects)
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Arnborg, Stefan; Corneil, Derek G.; Proskurowski, Andrzej, Complexity of finding embeddings in a k-tree, SIAM J. Algebr. Discrete Methods, 8, 2, 277-284, (1987) · Zbl 0611.05022
[2] Bodlaender, Hans L., Treewidth: algorithmic techniques and results, (Proceedings 22nd International Symposium on Mathematical Foundations of Computer Science, MFCS 1997, LNCS, vol. 1295, (1997), Springer), 19-36 · Zbl 0941.05057
[3] Bodlaender, Hans L.; Drange, Pål Grnås; Dregi, Markus S.; Fomin, Fedor V., Daniel lokshtanov, and michal pilipczuk. A \(c^k n\) 5-approximation algorithm for treewidth, SIAM J. Comput., 45, 2, 317-378, (2016) · Zbl 1333.05282
[4] Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C.A.; Kratsch, Dieter; Thilikos, Dimitrios M., On exact algorithms for treewidth, ACM Trans. Algorithms (TALG), 9, 1, 12, (2012) · Zbl 1301.05328
[5] Bodlaender, Hans L.; Koster, Arie M. C.A., Treewidth computations i. upper bounds, Inform. Comput., 208, 3, 259-275, (2010) · Zbl 1186.68328
[6] Bodlaender, Hans L.; Koster, Arie M. C.A., Treewidth computations ii. lower bounds, Inform. Comput., 209, 7, 1103-1119, (2011) · Zbl 1220.68071
[7] Bodlaender, Hans L.; Koster, Arie M. C.A.; Wolle, Thomas, Contraction and treewidth lower bounds, (Proceedings 12th Annual European Symposium on Algorithms, ESA 2004, LNCS, vol. 3221, (2004), Springer), 628-639 · Zbl 1111.68558
[8] Brinkmann, Gunnar; Coolsaet, Kris; Goedgebeur, Jan; Melot, Hadrien, House of graphs: A database of interesting graphs, Discrete Appl. Math., 161, 1, 311-314, (2013) · Zbl 1292.05254
[9] Cygan, Marek; Fomin, Fedor V.; Kowalik, Łukasz; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket, Parameterized algorithms, vol. 4, (2015), Springer · Zbl 1334.90001
[10] De Santo, Massimo; Foggia, Pasquale; Sansone, Carlo; Vento, Mario, A large database of graphs and its use for benchmarking graph isomorphism algorithms, Pattern Recognit. Lett., 24, 8, 1067-1079, (2003) · Zbl 1028.68040
[11] Holger Dell, The 1st parameterized algorithms and computational experiments challenge, 2016. See https://pacechallenge.wordpress.com/. · Zbl 1350.68118
[12] Diestel, Reinhard, Graph theory, Graduate Texts in Mathematics, (2005), Springer · Zbl 1074.05001
[13] Dijk, Thomas van; van den Heuvel, Jan-Pieter; Slob, Wouter, Computing treewidth with libtw. technical report, (2006), Utrecht University
[14] Gogate, Vibhav; Dechter, Rina, A complete anytime algorithm for treewidth, (Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, UAI 2004, (2004), AUAI Press), 201-208 · Zbl 1152.68560
[15] David S. Johnson, Michael Trick, Graph coloring instances, 1996. See http://mat.gsia.cmu.edu/COLOR/instances.html.
[16] Koster, Arie M. C.A.; Bodlaender, Hans L.; van Hoesel, Stan P. M., Treewidth: computational experiments, Electron. Notes Discrete Math., 8, 54-57, (2001) · Zbl 1409.05176
[17] Brendan D. McKay, Combinatorial data. See, http://users.cecs.anu.edu.au/ bdm/.
[18] McKay, Brendan D.; Piperno, Adolfo, Practical graph isomorphism, ii, J. Symbolic Comput., 60, 94-112, (2014) · Zbl 1394.05079
[19] Shoikhet, Kirill; Geiger, Dan, A practical algorithm for finding optimal triangulations, (Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Conference on Innovative Applications of Artificial Intelligence, AAAI 1997, (1997), AAAI Press), 185-190
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.