Technical Report 221-1989

Title

On the Pathwidth of Chordal Graphs

Author

Jens Gustedt

Publication

DISAM, vol. 45, 1993, pp. 233-248

Special issue for ARIDAM IV, 1989.

Source

The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de

Classification

not available

Keywords

not available

Abstract

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.