✦ LIBER ✦

Matching and multidimensional matching in chordal and strongly chordal graphs

✍ Scribed by Elias Dahlhaus; Marek Karpinski

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 877 KB
Volume: 84
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(98)00006-7

No coin nor oath required. For personal study only.

✦ Synopsis

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).

📜 SIMILAR VOLUMES

Maximum vertex-weighted matching in stro

Maximum vertex-weighted matching in strongly chordal graphs

✍ Manoel B. Campêlo; Sulamita Klein 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 412 KB

Given a graph G = (V, E) and a real weight for each vertex of G, the vertex-weight of a matching is defined to be the sum of the weights of the vertices covered by the matching. In this paper we present a linear time algorithm for finding a maximum vertex-weighted matching in a strongly chordal grap

Erratum to “Chordal bipartite, strongly

Erratum to “Chordal bipartite, strongly chordal, and strongly chordal bipartite graphs”: [Discrete Mathematics 260 (2003) 231–238]

✍ Terry A. McKee 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 70 KB

The parallel solution of domination prob

The parallel solution of domination problems on chordal and strongly chordal graphs

✍ Elias Dahlhaus; Peter Damaschke 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 975 KB

Steiner trees, connected domination and

Steiner trees, connected domination and strongly chordal graphs

✍ Kevin White; Martin Farber; William Pulleyblank 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 829 KB

Domination, independent domination, and

Domination, independent domination, and duality in strongly chordal graphs

✍ Martin Farber 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 1006 KB

Strong clique trees, neighborhood trees,

Strong clique trees, neighborhood trees, and strongly chordal graphs

✍ McKee, Terry A. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 1 views

Maximal complete subgraphs and clique trees are basic to both the theory and applications of chordal graphs. A simple notion of strong clique tree extends this structure to strongly chordal graphs. Replacing maximal complete subgraphs with open or closed vertex neighborhoods discloses new relationsh