An O(n) time algorithm for maximum matching in P4-tidy graphs

✍ Scribed by J.L. Fouquet; I. Parfenoff; H. Thuillier

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 630 KB
• Volume: 62
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00081-1

✦ Synopsis

The A-tidy graphs were introduced by I. Rusu to generalize some already known classes of graphs with "few" induced P4 s. In this paper, we extend to PA-tidy graphs a linear time algorithm of C.-H. Yang and M.-S. Yu for finding a maximum matching in a cograph G (given a parse tree associated to G). @