Quick search
Go!

RECOGNITION ALGORITM FOR P₄-TIDY GRAPHS


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

Issue:

SSRSMI, Number 2, Volume XXVI

Section:

Volume 26, Number 2

Abstract:

In this article we give a characterization of P₄-tidy graphs. We also give recognition algorithm for P₄-tidy graphs, comparable to existent ones as execution time. Finally, we determine the combinatorial optimization number in efficient time for P₄-tidy graphs. We show that for P4-tidy graphs clique problem is polynomial time.

Keywords:

P₄-tidy graphs, spider graphs, quasi-spider graphs, weak decomposition, recognition algorithm.

Code [ID]:

SSRSMI201602V26S01A0004 [0004497]

Full paper:

Download pdf


Copyright (c) 1995-2007 University of Bacu