𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximum Induced Matchings for Chordal Graphs in Linear Time

✍ Scribed by Andreas Brandstädt; Chính T. Hoàng

Publisher
Springer
Year
2007
Tongue
English
Weight
263 KB
Volume
52
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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.

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