MATCHING AND MULTIDIMENSIONAL MATCHING IN CHORDAL AND STRONGLY CHORDAL GRAPHS

Chordal graphs are graphs with the property that each cycle of length greater than 3 has two non-consecutive vertices that are joined by an edge. An important subclass of chordal graphs are strongly chordal gra phs (Farber, 1983). Chordal graphs appear for example in the design of acyclic data base schemes (Beeri et al., 1983). In this paper we stud y the computational complexity (both sequential and parallel) of the m aximum matching problem for chordal and strongly chordal graphs. We sh ow that there is a linear-time greedy algorithm for a maximum matching in a strongly chordal graph provided a strongly perfect elimination o rdering is known. This algorithm can also be turned into a parallel al gorithm. The technique used can also be extended to the perfect multid imensional matching for chordal and strongly chordal graphs yielding t he first polynomial time algorithms for these classes of graphs (the m ultidimensional matching is NP-complete in general). (C) 1998 Elsevier Science B.V. All rights reserved.