𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximum vertex-weighted matching in strongly chordal graphs

✍ Scribed by Manoel B. Campêlo; Sulamita Klein

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
412 KB
Volume
84
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

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 graph, given a strong elimination ordering. The algorithm can be specialized to find a maximum cardinality matching, yielding an algorithm similar to one proposed earlier by Dahlhaus and Karpinsky. The technique does not seem to apply to the case of general cdgcweighted matchings.

📜 SIMILAR VOLUMES

Matching and multidimensional matching i
Matching and multidimensional matching in chordal and strongly chordal graphs
✍ Elias Dahlhaus; Marek Karpinski 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 877 KB

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 s

Maximum induced matchings in graphs
Maximum induced matchings in graphs
✍ Jiping Liu; Huishan Zhou 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 218 KB

We provide a formula for the number of edges of a maximum induced matching in a graph. As applications, we give some structural properties of (k + 1 )K2-free graphs, construct all 2K2-free graphs, and count the number of labeled 2K2-free connected bipartite graphs.

Finding dominating cliques efficiently,
Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
✍ Dieter Kratsch 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 914 KB

We study a new version of the domination problem in which the dominating set is required to be a clique. The minimum dominating clique problem is NP-complete for split graphs and, hence, for chordal graphs. We show that for two other important subclasses of chordal graphs the problem is solvable eff