Issue:

SSRSMI, Number 1, Volume XXVI

Section:

Volume 26, Number 1

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.

Keywords:

chordal graphs, doubly chordal graphs, dually chordal graphs, hereditary dually chordal graphs, strongly chordal graphs, weak decomposition, recognition algorithm.

Code [ID]:

SSRSMI201601V26S01A0010 [0004438]

Full paper:

Download pdf