TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen1989

COGA 5-Wheel

Inhalt

zur Navigation

Preprints 1989

On the Pathwidth of Chordal Graphs
Zitatschlüssel Report-221-1989
Autor Jens Gustedt
Seiten 233-248
Jahr 1989
Journal Discrete Applied Mathematics, 1990
Jahrgang 45
Nummer 221
Notiz Special issue for ARIDAM IV, 1989.
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung In this paper we first show that the path width problem for chordal graphs is $\cal NP$-hard. Then we give polynomial algorithms for two subclasses to enlight the structural reasons for the intractibility of the problem. One of those classes are the $k$-starlike graphs – a generalization of split graphs. The other class are the primitive starlike graphs – a class of graphs where the intersection behaviour of maximal cliques is strongly restricted.
Typ der Publikation Preprint
Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe