Dahlhaus, Elias
(1999).
Minimum Fill-in and Treewidth for Graphs Modularly Decomposable into Chordal Graphs.
['eprint_fieldopt_monograph_type_preprint' not defined].
Preview |
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: | Monograph (['eprint_fieldopt_monograph_type_preprint' not defined]) |
| Creators: | Creators Email ORCID ORCID Put Code Dahlhaus, Elias UNSPECIFIED UNSPECIFIED UNSPECIFIED |
| 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 |