𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A simple matching algorithm for regular bipartite graphs

✍ Scribed by Kazuhisa Makino; Takashi Takabatake; Satoru Fujishige

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
62 KB
Volume
84
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the perfect matching problem for a βˆ†-regular bipartite graph with n vertices and m edges, i.e., 1 2 nβˆ† = m, and present a new O(m + n log n log βˆ†) algorithm. Cole and Rizzi, respectively, gave algorithms of the same complexity as ours, Schrijver also devised an O(mβˆ†) algorithm, and the best existing algorithm is Cole, Ost, and Schirra's O(m) algorithm. Extending Gabow's perfect matching algorithm for 2 t -regular bipartite graph with a positive integer t and using Cole and Hopcroft's edge-sparsification technique, we show another approach to the perfect matching problem, which results in a simple algorithm that employs no sophisticated data structure such as dynamic tree and splay tree.

πŸ“œ SIMILAR VOLUMES

The rainbow number of matchings in regul
The rainbow number of matchings in regular bipartite graphs
✍ Xueliang Li; Zhixia Xu πŸ“‚ Article πŸ“… 2009 πŸ› Elsevier Science 🌐 English βš– 386 KB

Given a graph G and a subgraph H of G, let rb(G, H) be the minimum number r for which any edge-coloring of G with r colors has a rainbow subgraph H. The number rb(G, H) is called the rainbow number of H with respect to G. Denote as mK 2 a matching of size m and as B n,k the set of all the k-regular

Simple Markov-chain algorithms for gener
Simple Markov-chain algorithms for generating bipartite graphs and tournaments
✍ Ravi Kannan; Prasad Tetali; Santosh Vempala πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 174 KB πŸ‘ 2 views

We consider two problems: randomly generating labeled bipartite graphs with a given degree sequence and randomly generating labeled tournaments with a given score sequence. We analyze simple Markov chains for both problems. For the first problem, we cannot prove that our chain is rapidly mixing in g