# 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: |
Postscript
Download (190kB) | Preview |
---|---|

Export as: | [error in script] |

Editorial actions: |
View Item (Login required) |

Content information:

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 |