Minimum Fill-in and Treewidth for Graphs Modularly Decomposable into Chordal Graphs

Dahlhaus, Elias (1999) Minimum Fill-in and Treewidth for Graphs Modularly Decomposable into Chordal Graphs.
Technical Report , 13 p.

Abstract

We show that a minimum fill-in ordering of a graph can be determined in linear time if it can be modularly decomposed into chordal graphs. This generalizes results of L. Babel: Triangulating Graphs with few P4s. We show that the treewidth of these graphs can be determined in O((n+m)log n) time.


Actions:
Download: [img] Postscript
Download (190kB) | Preview
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: [error in script]
Depositing User: Archive Admin
Date Deposited: 16 Sep 2002 00:00
Last Modified: 20 Dec 2011 11:39
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/355