𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Bipartite graph matching for points on a line or a circle

✍ Scribed by Michael Werman; Shmuel Peleg; Robert Melter; T.Y Kong

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
376 KB
Volume
7
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Excluding a bipartite circle graph from
Excluding a bipartite circle graph from line graphs
✍ Sang-il Oum 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 215 KB

## Abstract We prove that, for a fixed bipartite circle graph __H__, all line graphs with sufficiently large rank‐width (or clique‐width) must have a pivot‐minor isomorphic to __H__. To prove this, we introduce graphic delta‐matroids. Graphic delta‐matroids are minors of delta‐matroids of line grap

A simple matching algorithm for regular
A simple matching algorithm for regular bipartite graphs
✍ Kazuhisa Makino; Takashi Takabatake; Satoru Fujishige 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 62 KB

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 b

A note on the number of perfect matching
A note on the number of perfect matchings of bipartite graphs
✍ Zhang Fuji; Zhang Heping 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 484 KB

Let G be a bipartite graph with 2n vertices, A its adjacency matrix and K the number of perfect matchings. For plane bipartite graphs each interior face of which is surrounded by a circuit of length 4s + 2, s E { 1,2,. . .}, an elegant formula, i.e. det A = (-1 )nK2, had been rigorously proved by Cv