Dahlhaus, Elias
(1999).
Minimum Fill-in and Treewidth for Graphs Modularly Decomposable into Chordal Graphs.
["eprint_fieldopt_monograph_type_preprint" not defined].
|
PDF
zaik1999-355.pdf - Draft Version Download (211kB) | Preview |
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.
| Item Type: | Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined]) | ||||||||
| Creators: |
|
||||||||
| URN: | urn:nbn:de:hbz:38-548390 | ||||||||
| Journal or Publication Title: | "" | ||||||||
| Series Name: | Lecture notes in computer science | ||||||||
| Volume: | 1517 | ||||||||
| Page Range: | pp. 713-724 | ||||||||
| Date: | 1999 | ||||||||
| Language: | English | ||||||||
| Faculty: | Faculty of Mathematics and Natural Sciences | ||||||||
| Divisions: | Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science | ||||||||
| Subjects: | Data processing Computer science | ||||||||
| Refereed: | No | ||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/54839 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |