| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420555 | Discrete Applied Mathematics | 2009 | 13 Pages |
Abstract
We present a new representation of a chordal graph called the clique-separator graph , whose nodes are the maximal cliques and minimal vertex separators of the graph. We present structural properties of the clique-separator graph and additional properties when the chordal graph is an interval graph, proper interval graph, or split graph. We also characterize proper interval graphs and split graphs in terms of the clique-separator graph. We present an algorithm that constructs the clique-separator graph of a chordal graph in O(n3)O(n3) time and of an interval graph in O(n2)O(n2) time, where nn is the number of vertices in the graph.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Louis Ibarra,