direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 1990

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