Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142341 | Operations Research Letters | 2013 | 5 Pages |
Abstract
In this paper, a representation for chordal graphs called the compact representation, based on the running intersection property, is presented. It provides the means to immediately deduce several structural properties of a chordal graph such as a perfect elimination ordering, the minimal vertex separators and a clique-tree. These properties support an efficient algorithm for the construction of the compact representation. Simple characterizations of some subclasses of chordal graphs can be obtained using this representation.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Lilian Markenzon, Christina Fraga Esteves Maciel Waga, Paulo Renato da Costa Pereira, Clícia Valladares Peixoto Friedmann, Abel Rodolfo Garcia Lozano,