Quick search
Go!

GENERALIZATIONS OF TRIANGULATED GRAPHS


MIHAI TALMACIU
Department of Mathematics, Informatics and Education Sciences, Faculty of Sciences, "Vasile Alecsandri" University of Bacău, Calea Mărăşeşti 157, Bacău 600115, ROMANIA, e-mail: mtalmaciu@ub.ro, mihaitalmaciu@yahoo.com

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]

DOI:

Full paper:

Download pdf


Copyright (c) 1995-2007 University of Bacãu