Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases

 Access to full text

 Full (PDF)

1. H. Alt, N. Blum, K. Mehlhron and M. Paul, Computing a maximum cardinality matching in a bipartite graph in time $O(n^{1.5}\sqrt{m/logn}$ ). Inform. Process. Lett.37 (1991) 237-240.  
2. E. Bampis, A. Giannakos, A. Karzanov, I. Milis and Y. Manoussakis, Matchings in cubic graphs are as difficult as in general graphs, Rapport de Recherche No. 12. LaMI, Université d' Evry - Val d'Essonne (1995).  
3. R. Cole and U. Vishkin, Approximate and exact parallel scheduling, Part 1: The basic technique with applications to optimal parallel list ranking in logarithmic time. SIAM J. Comput.17 (1988) 128-142.  
4. N. Chiba, T. Nishizeki and N. Saito, Applications of the planar separator theorem. J. Inform. Process.4 (1981) 203-207.  
5. E. Dahlhaus and M. Karpinski, Perfect matching for regular graphs is AC0-hard for the general matching problem. J. Comput. System Sci.44 (1992) 94-102.  
6. J. Edmonds, Paths, trees and flowers. Canad. J. Math.17 (1965) 449-467.  
7. T. Feder and R. Motwani, Clique partitions, graph compression and speeding-up algorithms, ${23}^{\mathrm{th}}$ STOC (1991) 123-133.  
8. A. Goldberg, S. Plotkin and M. Vaidya, Sublinear time parallel algorithms for matchings and related problems. J. Algorithms14 (1993) 180-213.  
9. R. Greenlaw and R. Petreschi, Cubic graphs. ACM Computing Surveys27 (1995) 471-495.  
10. D.Yu. Grigoriev and M. Karpinski, The matching problem for bipartite graphs with polynomially bounded permanents is in NC, ${28}^{\mathrm{th}}$ FOCS (1987) 166-172.  
11. T. Hagerup, Optimal parallel algorithms on planar graphs. Inform. and Comput.84 (1990) 71-96.  
12. M. Karpinski and W. Rytter, Fast parallel algorithms for graph matching problems. Oxford University Press, preprint (to appear).  
13. G. Lev, N. Pippenger and L. Valiant, A fast parallel algorithm for routing in permutation networks. IEEE Trans. Comput.C-30 (1981) 93-100.  
14. Y.D. Liang, Finding a maximum matching in a circular-arc graph. Inform. Process. Lett.35 (1993) 185-193.  
15. L. Lovasz and M. Plummer, Matching Theory. Elsevier Science Publishers (1986).  
16. S. Micali and V.V. Vazirani, An $O\left(\right|V{|}^{\frac{1}{2}}\left|E\right|)$ algorithm for finding maximum matchings in general graphs, ${21}^{\mathrm{th}}$ FOCS (1980) 17-23.  
17. G.L. Miller and J. Naor, Flow in planar graphs with multiply sources and sinks, Proc. ${30}^{\mathrm{th}}$ FOCS (1989) 112-117.  
18. A. Moitra and R. Jonhson, Parallel algorithms for maximum matching and other problems in interval graphs, TR 88-927. Cornell University (1988).  
19. K. Mulmuley, U.V. Vazirani and V.V. Vazirani, Matching is as easy as matrix inversion. Combinatorica7 (1987) 105-113.  
20. T. Nishizeki and N. Chiba, Planar Graphs: Theory and Algorithms. North-Holland (1988).  
21. O. Ore, The four color problem. Academic Press, New York (1967).  
22. M.D. Plummer, Matching and vertex packing: how ``hard" are they?, Quo Vadis, Graph Theory?, edited by J. Gimbel, J.W. Kennedy and L.V. Quintas. Ann. Discrete Math.55 (1993) 275-312.  
23. S.V. Ramachandran and J.H. Reif, An optimal parallel algorithm for graph planarity, ${30}^{\mathrm{th}}$ FOCS (1989) 282-287.  
24. M.O. Rabin, Maximum matching in general graphs through randomization. J. Algorithms10 (1989) 557-567.  
25. V.V. Vazirani, NC algorithms for computing the number of perfect matchings in K3,3-free graphs and related problems. Inform. and Comput.80 (1989) 152-164.  
26. V.V. Vazirani, A theory of alternating paths and blossoms for proving correctness of the $O\left(\sqrt{V}E\right)$ general graph maximum matching algorithm. Combinatorica14 (1994) 71-109.