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:
Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
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