Recently Rim van Wersch en myself launched ToTo, an open database for computation, storage and retrieval of tree decompositions.
A short description of its functionality is provided below. (See also the accompanying article in Discrete Applied Mathematics).
The website can be accessed at the following URL:
- http://treedecompositions.com
We are naturally keen to receive feedback of any kind from the discrete mathematics and graph theory communities. This will help us improve the database in the future. Should the database prove popular we will seek funding to improve the computational power and storage capacity of the server that sits behind ToTo.
Please send any feedback to both Rim (rim@treedecompositions.com) and myself (steven.kelk@maastrichtuniversity.nl).
Kind regards,
Steven Kelk
http://skelk.sdf-eu.org
Assistant Professor, Department of Data Science and Knowledge Engineering (DKE)
Maastricht University, Netherlands
Announcing ToTo, an open database for computation, storage and retrieval of tree decompositions.
At Toto we host an open collection of graphs and their tree decompositions. Its main feature is an automated treewidth webservice, which users can query to obtain a reasonable tree decomposition for their input graph. If the graph is known in the database, its corresponding tree decomposition is returned. If it's a new graph, a heuristic decomposition is computed on-the-fly and returned to the user, while the graph and this composition are added to the database for future reference and improvement.
Users can also submit improved tree decompositions for graphs to the database (in PACE16 TD format). If the submitted decomposition improves upon the current best width, it is stored as the new upper bound for the graph. The submitted decomposition is also mapped to the canonical isomorphism of the graph and stored, so any future queries to isomorphic graphs benefit from the canonized submission. The database can be used as a quick lookup tool as well as a repository for tree decompositions. New graphs are made available to other users by simply looking them up, while the database can be queried for interesting instances e.g. graphs where the gap between the best known lower bound and upper bound is large.
- More information on ToTo and its functionalities is given in:
"ToTo: An open database for computation, storage and retrieval of tree decompositions"
Discrete Applied Mathematics, Article in Press
Available online: http://dx.doi.org/10.1016/j.dam.2016.09.023
- A preprint is available here:
http://treedecompositions.com/TotoTreewidthDatabase_VanWersch_Kelk.pdf
- ToTo itself can be accessed at: http://treedecompositions.com/
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
