A linear time algorithm for the maximum matching problem on cographs |
| |
| Authors: | Ming-Shing Yu Cheng-Hsing Yang |
| |
| Affiliation: | (1) Department of Applied Mathematics, National Chung-Hsing University, 40227 Taichung, Taiwan |
| |
| Abstract: | ![]()
In this paper, we develop a sequential algorithm for the maximum matching problem on cographs. The input is a parse tree of some cograph. The time complexity of our algorithm is linear.Supported by National Science Council of Taiwan, R.O.C. under Grant NSC81-0415-E-005-03. |
| |
| Keywords: | F.2.2 G.2.2 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
