Minimum Fill-in and Treewidth for Graphs Modularly Decomposable into Chordal Graphs
Dahlhaus, Elias
(1998)
Minimum Fill-in and Treewidth for Graphs Modularly Decomposable into Chordal Graphs.
Published In:
Graph-theoretic concepts in computer science : 24th international workshop, WG '98, Smolenice Castle, Slovak Republic, June 18 - 20, 1998 ; proceedings, Lecture notes in computer science. 1517 Springer 1998, pp. 713-724.
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:
Content information:
Deposit Information:
ZAIK Number: | zaik1999-355a |
---|---|
Depositing User: | Archive Admin |
Date Deposited: | 05 Dec 2011 11:00 |
Last Modified: | 05 Dec 2011 11:00 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/355001 |