𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximum matchings in general graphs through randomization

✍ Scribed by Michael O Rabin; Vijay V Vazirani

Publisher
Elsevier Science
Year
1989
Tongue
English
Weight
679 KB
Volume
10
Category
Article
ISSN
0196-6774

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 matchings in sparse random graph
Maximum matchings in sparse random graphs: Karp–Sipser revisited
✍ Jonathan Aronson; Alan Frieze; Boris G. Pittel πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 490 KB πŸ‘ 1 views

We study the average performance of a simple greedy algorithm for finding a matching in a sparse random graph G , where c ) 0 is constant. The algorithm was first n, c r n w proposed by Karp and Sipser Proceedings of the Twenty-Second Annual IEEE Symposium on x Foundations of Computing, 1981, pp. 3

Local maximum stable sets in bipartite g
Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
✍ Vadim E. Levit; Eugen Mandrescu πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 233 KB

A maximum stable set in a graph G is a stable set of maximum size. S is a local maximum stable set of G, and we write S ∈ (G), if S is a maximum stable set of the subgraph spanned by S βˆͺ N (S), where N (S) is the neighborhood of S. A matching M is uniquely restricted if its saturated vertices induce