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 appro...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2017-01, Vol.217, p.389-393
Main Authors: van Wersch, Rim, Kelk, Steven
Format: Article
Language:English
Subjects:
Algorithms
Computation
Decomposition
Graphs
Retrieval
Studies
Tree decomposition
Trees
Treewidth
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2016.09.023