Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1994 Copyright 1994 Universität Bonn, Institut für Informatik, Abt. V
85107

On the Sequential and Parallel Complexity of Matching in Chordal and Strongly Chordal Graphs
Elias Dahlhaus, Marek Karpinski
[Download PostScript] [Download PDF]

In this paper we consider the sequential and parallel complexity of the maximum matching problem in chordal and strongly chordal graphs. We prove that, given a strongly perfect elimination ordering, a maximum matching in a strongly chordal graph can be found in a linear time. On the other hand we observe that the matching problem restricted to chordal (paths) graphs is of the same parallel complexiy as a general bipartite matching.

Last Change: 08/18/99 at 13:00:38
 English
Universität Bonn -> Institut für Informatik -> Abteilung V