Opening book details…
Can I read Matching and Multidimensional Matching in Chordal and Strongly Chordal Graphs on EtoBox?
Matching and Multidimensional Matching in Chordal and Strongly Chordal Graphs by Elias Dahlhaus; Marek Karpinski is a Computer Science article available to read on EtoBox.
What is Matching and Multidimensional Matching in Chordal and Strongly Chordal Graphs about?
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 graphs (Farber, 1983). Chordal graphs appear for example in the design of acyclic data base schemes (Beeri et al., 1983). 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 also be turned into a parallel algorithm. The technique used can also be extended to the perfect 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).
Who reads Matching and Multidimensional Matching in Chordal and Strongly Chordal Graphs?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Elias Dahlhaus; Marek Karpinski
- Publisher
- Elsevier Science; Elsevier ; Elsevier BV (ISSN 0166-218X)
- Published
- 1998
- Language
- EN
- Field
- Computer Science (Physical Sciences)