swMATH ID: 19369
Software Authors: van Wersch, Rim; Kelk, Steven
Description: ToTo: an open database for computation, storage and retrieval of tree decompositions. 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 {sc 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.
Homepage: http://www.sciencedirect.com/science/article/pii/S0166218X16304164
Keywords: treewidth; tree decomposition; graphs; database; algorithms
Related Software: Jdrasil; dynASP; Regina; LibTW; ComputeTW; Traces; House of Graphs; nauty
Referenced in: 4 Publications

Referencing Publications by Year