On the Computational Complexity of Matching on Chordal and Strongly Chordal Graphs
| Title | On the Computational Complexity of Matching on Chordal and Strongly Chordal Graphs |
| Publication Type | Technical Report |
| Year of Publication | 1994 |
| Authors | Dahlhaus, E., & Karpinski M. |
| Other Numbers | 913 |
| Abstract | In this paper we study the computational complexity (both sequential and parallel) of the maximum matching problem for chordal and strongly chordal graphs. We show that there is a linear time greedy algorithm for a maximum matching in a strongly chordal graph provided a strongly perfect elimination ordering is known. This algorithm can be also turned into a parallel algorithm. The technique used can be also extended for the multidimensional matching for chordal and strongly chordal graphs yielding the first polynomial time algorithms for these classes of graphs (the multidimensional matching is NP-complete in general). |
| URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1994/tr-94-043.pdf |
| Bibliographic Notes | ICSI Technical Report TR-94-043 |
| Abbreviated Authors | E. Dahlhaus and M. Karpinski |
| ICSI Publication Type | Technical Report |