Paper Info
Title
A new NC-algorithm for finding a perfect matching in d-regular bipartite graphs when d is small
Abstract
The perfect matching problem for general graphs reduces to the same for regular graphs. Even finding an NC algorithm for the perfect matching problem in cubic (3-regular) or 4-regular graphs will suffice to solve the general problem (see [DK 92]). For regular bipartite graphs an NC algorithm is already known [LPV 81], while [SW 96] give an NC algorithm for cubic-bipartite graphs. We present a new and conceptually simple parallel algorithm for finding a perfect matching in d-regular bipartite graphs. When d is small (polylogarithmic) our algorithm in fact runs in NC. In particular for cubic-bipartite graphs, our algorithm as well as its analysis become much simpler than the previously known algorithms for the same. Our techniques are completely different from theirs. Interestingly, our algorithm is based on a method used by [MV 00] for finding a perfect matching in planar-bipartite graphs. So, it is remarkable that, circumventing the planarity, we could still make the same approach work for a non-planar subclass of biparitite graphs.
Year
DOI
Venue
2006
10.1007/11758471_30
CIAC
Keywords
DocType
Volume
general graph,general problem,perfect matching problem,new nc-algorithm,nc algorithm,regular graph,perfect matching,d-regular bipartite graph,regular bipartite graph,cubic-bipartite graph,conceptually simple parallel algorithm,bipartite graph,parallel algorithm
Conference
3998
ISSN
ISBN
Citations 
0302-9743
3-540-34375-X
0
PageRank 
References 
Authors
0.34
8
1
Name
Order
Citations
PageRank
Raghav Kulkarni117219.48