A simple matching algorithm for regular bipartite graphs.
type: Item
instance of: scholarly article
title: A simple matching algorithm for regular bipartite graphs.
zbMATH Open document ID: 1042.68095
DOI: 10.1016/S0020-0190(02)00273-9
author: Kazuhisa Makino
author: Takashi Takabatake
author: Satoru Fujishige
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
review text: We consider the perfect matching problem for a \(\Delta\)-regular bipartite graph with \(n\) vertices and \(m\) edges, i.e., \(\frac12n\Delta=m\), and present a new \(O(m+n\log n\log\Delta)\) algorithm. Cole and Rizzi, respectively, gave algorithms of the same complexity as ours, Schrijver also devised an \(O(m\Delta)\) 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.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 1856474
zbMATH Keywords: Bipartite matching
zbMATH Keywords: Edge-coloring
zbMATH Keywords: Graph algorithms
MaRDI profile type: Publication
cites work: On Edge Coloring Bipartite Graphs
cites work: Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
cites work: A matching algorithm for regular bipartite graphs
cites work: Using euler partitions to edge color bipartite multigraphs
cites work: Edge-Coloring Bipartite Graphs
cites work: Bipartite Edge Coloring in $O(\Delta m)$ Time
full work available at URL: s0020-0190(02)00273-9
OpenAlex ID: W1977306381
description: scientific article; zbMATH DE number 1856474