Abstract
Using weak decomposition, we characterize in a unified manner the classes of doubly chordal, of hereditary dually chordal and of strongly chordal graphs. We also give a recognition algorithm that is applicable for doubly chordal graphs, for hereditary dually chordal and for strongly chordal graphs. In addition, we determine the combinatorial op-timization numbers in efficient time for all the above classes of graphs.
Cuvinte cheie
chordal graphs
doubly chordal graphs
dually chordal graphs
hereditary dually chordal graphs
strongly chordal graphs
weak decomposition
recognition algorithm