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>