Computing the Treewidth and the Minimum Fill-In with the Modular Decomposition |
| |
Authors: | Hans L. Bodlaender and Udi Rotics |
| |
Affiliation: | (1) Institute of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands. hansb@cs.uu.nl., NL;(2) School of Mathematics and Computer Science, Netanya Academic College, P.O. Box 120, 42100 Netanya, Israel. rotics@mars.netanya.ac.il., IL |
| |
Abstract: | Abstract. Using the notion of modular decomposition we extend the class of graphs on which both the treewidth and the minimum fill-in can be solved in polynomial time. We show that if C is a class of graphs that are 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 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 3 ) time for treewidth and minimum fill-in. |
| |
Keywords: | . Treewidth Minimum fill-in Modular decomposition Minimal separators Polynomial algorithms Graph algorithms. |
本文献已被 SpringerLink 等数据库收录! |
|