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)
Content information:
Item Type: Proceedings article
Citations: 4 (Google Scholar) |
Uncontrolled Keywords: chordal graphs efficient algorithms minimum fill-in modular decomposition
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C75 Structural characterization of types of graphs

  • 05-XX Combinatorics > 05Cxx Graph theory > 05C85 Graph algorithms

  • 68-XX Computer science > 68Qxx Theory of computing > 68Q25 Analysis of algorithms and problem complexity

  • 68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R10 Graph theory

    		•
    Divisions: Mathematical Institute
    Related URLs:
    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