AN O(N) TIME ALGORITHM FOR MAXIMUM MATCHING IN P-4-TIDY GRAPHS

Authors
FOUQUET JL PARFENOFF I THUILLIER H
Citation
Jl. Fouquet et al., AN O(N) TIME ALGORITHM FOR MAXIMUM MATCHING IN P-4-TIDY GRAPHS, Information processing letters, 62(6), 1997, pp. 281-287
Citations number
15
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
62
Issue
6
Year of publication
1997
Pages
281 - 287
Database
ISI
SICI code
0020-0190(1997)62:6<281:AOTAFM>2.0.ZU;2-Z
Abstract
The P-4-tidy graphs were introduced by I. Rusu to generalize some alre ady known classes of graphs with ''few'' induced P-4 s. In this paper, we extend to P-4-tidy graphs a linear time algorithm of C.-H. Yang an d M.-S. Yu for finding a maximum matching in a cograph G (given a pars e tree associated to G). (C) 1997 Elsevier Science B.V.