Nada

^ Up to Research, Theory group at Nada, KTH.

Graphs and Decomposability

Researchers

Ph.D. students

Short description

Most combinatorial computations on graphs are difficult. If one restricts the type of graphs under consideration, some of these problems admit fast algorithms. For any fixed k, graphs of tree-width at most k (or partial k-trees) is one family of graphs on which most combinatorial optimization problems admit fast algorithms. We have given very general conditions that ensure the existence of linear time solution algorithms for computational problems on partial k-trees. We have also studied the tree-decomposition problem, and developed methods that for many classes of graphs give explicit bounds on the size of obstructions. We developed prototype software for translating logic statements of computational problems to automata solving them for decomposed graphs, and applied the method for AI reasoning. A current project involves generalized decompositions related to modular decomposition, clique-width and NLC-width.

Funding

The project has been funded 1993-1997 by TFR.

Selected publications

Arnborg, S., Courcelle, B., Proskurowski, A., Seese, D., An algebraic theory of graph reduction, JACM, 40 (5) 1993, 1134-1164.
Arnborg, S., Lagergren, J., Seese, D., Problems easy for tree-decomposable graphs, J. of Algorithms 12 (1991), 308-340.
Arnborg, S., Graph decompositions and tree automata in reasoning with uncertainty. J. Expt. Theor. Artif. Intell. 5 (1993), 335– 357.
Lagergren, J., An upper bound on the size of an obstruction, AMS Contemporary Mathematics series 147 (1993) 601-621.
Lagergren, J., The non existence of reduction rules giving an embedding in a k-tree, Annals of Discrete Mathematics, 54 (2-3) Oct 1994 pp 219-224
Arnborg, S., Decomposable structures, boolean function representations, and optimization, MFCS 1995, LNCS 969, 21-36.
Courcelle, B. and Lagergren, J., Equivalent definitions of recognizability for sets of graphs of bounded tree-width. Mathematical Structures in Computer Science, 2:141--165,1996.
Jens Lagergren, Upper bounds on the size of obstructions and intertwines. Journal of Combinatorial Theory Series B, 73(1):7--40, May 1998.
Johansson, ÷., Clique-Decomposition, NLC-Decomposition, and Modular Decomposition - Relationships and Results for Random Graphs, Congressus Numerantium 132 (1998), 39-60.
Johansson, ÷., NLC2-decomposition in polynomial time, in Proc. 25th Int. Workshop on Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science 1665 (Springer, Berlin, 1999), 110-121.

^ Up to Research, Theory group at Nada, KTH.


Responsible for this page: Stefan Arnborg <stefan@nada.kth.se>
Latest change November 10, 1999
Technical support: <webmaster@nada.kth.se>