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

被引：7
作者：
Fouquet, JL
Parfenoff, I
Thuillier, H
机构：
[1] UNIV ORLEANS,LIFO,F-45067 ORLEANS 2,FRANCE
[2] UNIV MAINE,F-72017 LE MANS,FRANCE
来源：
INFORMATION PROCESSING LETTERS | 1997年 / 62卷 / 06期
关键词：
algorithms; graphs; matching; modular decomposition;
D O I：
10.1016/S0020-0190(97)00081-1
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The P-4-tidy graphs were introduced by I. Rusu to generalize some already 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 and M.-S. Yu for finding a maximum matching in a cograph G (given a parse tree associated to G). (C) 1997 Elsevier Science B.V.
引用
收藏
页码：281 / 287
页数：7
相关论文
共 15 条
[1]   2 THEOREMS IN GRAPH THEORY [J].
BERGE, C .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1957, 43 (09) :842-844
[2]  
BONDY JA, 1979, GRAPH THEORY APPLICA
[3]  
Cournier A., 1994, LECT NOTES COMPUTER, V787, P68
[4]  
CUNNINGHAM WH, CAN J MATH, V32, P734
[5]  
Giakoumakis V., 1997, Discrete Mathematics and Theoretical Computer Science, V1, P17
[6]  
HOANG CT, 1985, THESIS MONTREAL
[7]   ON A UNIQUE TREE-REPRESENTATION FOR P4-EXTENDIBLE GRAPHS [J].
JAMISON, B ;
OLARIU, S .
DISCRETE APPLIED MATHEMATICS, 1991, 34 (1-3) :151-164
[8]  
JAMISON B, 1989, STUD APPL MATH, V81, P89
[9]   A TREE-REPRESENTATION FOR P4-SPARSE GRAPHS [J].
JAMISON, B ;
OLARIU, S .
DISCRETE APPLIED MATHEMATICS, 1992, 35 (02) :115-129
[10]   AN OPTIMAL PARALLEL MATCHING ALGORITHM FOR COGRAPHS [J].
LIN, R ;
OLARIU, S .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1994, 22 (01) :26-36
12