ALCOMFT-TR-02-62

Hans L. Bodlaender and Udi Rotics
Computing the treewidth and the minimum fill-in with the modular decomposition
Utrecht. Work package 4. May 2002.

Abstract: Using the notion of modular decomposition we extend the class of graphs on which both the TREEWIDTH and the MINIMUM-FILL-IN problems can be solved in polynomial time. We show that if C is a class of graphs which is modularly decomposable into graphs that have a polynomial number of minimal separators, or graphs formed by adding a matching between two cliques, then both the TREEWIDTH and the MINIMUM-FILL-IN problems on C can be solved in polynomial time. For the graphs that are modular decomposable into cycles we give algorithms, that use respectively O(n) and O(n³) time for TREEWIDTH and MINIMUM FILL-IN.

Postscript file: ALCOMFT-TR-02-62.ps.gz (156 kb).