Perfect matching in general vs. cubic graphs : a note on the planar and bipartite cases

 Access to full text

 Full (PDF)

1. [1] H. Alt, N Blum K. Mehlhron, and M. Paul, Computing a maximum cardinality matching in a bipartite graph in time O(n1.5√ m/log n ). Inform. Process. Lett. 37 (1991) 237-240. Zbl0714.68036MR1095712
2. [2] E. Bampis, A. Giannakos, A. Karzanov, I. Milis and Y Manoussakis, Matchings in cubic graphs are as difficult as in general graphs, LaMI, Université d' Evry - Val d'Essonne (1995). Zbl0959.05092
3. [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. Zbl0637.68038MR925193
4. [4] N. Chiba, T. Nishizeki and N. Saito, Applications of the planar separator theorem. J. Inform. Process. 4 (1981) 203-207. Zbl0477.68069MR652015
5. [5] E. Dahlhaus and M. Karpinski, Perfect matching for regular graphs is AC°-hard for the general matching problem. J. Comput. System Sci. 44 (1992) 94-102. Zbl0743.68072MR1161106
6. [6] J. Edmonds, Paths, trees and flowers Canad. J. Math. 17 (1965) 449-467. Zbl0132.20903MR177907
7. [7] T. Feder and R. Motwani, Clique partitions, graph compression and speeding-up algorithms, 23th STOC (1991) 123-133. Zbl0831.68073
8. [8] A. Goldberg, S. Plotkin and M. Vaidya, Sublinear time parallel algorithms for matchings and related problems. J. Algorithms 14 (1993) 180-213. Zbl0769.68034MR1201924
9. [9] R. Greenlaw and R. Petreschi, Cubic graphs. ACM Computing Surveys 27 (1995) 471-495. 
10. [10] D. Yu. Grigoriev and M. Karpinski, The matching problem for bipartite graphs with polynomially bounded permanents is in NC, 28th FOCS (1987) 166-172. 
11. [11] T. Hagerup, Optimal parallel algorithms on planar graphs. Inform. and Comput 84 (1990) 71-96. Zbl0689.68056MR1032155
12. [12] M. Karpinski and W. Rytter, Fast parallel algorithms for graph matching problems. Oxford University Press, preprint (to appear). Zbl0895.05050MR1627822
13. [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. Zbl0455.94047MR605719
14. [14] Y. D. Liang, Finding a maximum matching in a circular-arc graph. Inform. Process. Lett. 35 (1993) 185-193. Zbl0768.68159MR1211528
15. [15] L. Lovasz and M. Plummer, Matching Theory. Elsevier Science Publishers (1986). Zbl0618.05001MR859549
16. [16] S. Micali and V.V. Vazirani, An O(|V|½|E|) algorithm for finding maximum matchings in general graphs, 21th FOCS (1980) 17-23. 
17. [17] G. L. Miller and J. Naor, Flow in planar graphs wüh multiply sources and sinks, Proc. 30th FOCS (1989) 112-117. 
18. [18] A. Moitra and R. Jonhson, Parallel algorithms for maximum matching and other problems in interval graphs, TR 88-927. Cornell University (1988). 
19. [19] K. Mulmuley, U. V. Vazirani and V. V. Vazirani, Matching is as easy as matrix inversion. Combinatorica 7 (1987) 105-113. Zbl0632.68041MR905157
20. [20] T. Nishizeki and N. Chiba, Planar Graphs: Theory and Algorithms. North-Holland (1988). Zbl0647.05001MR941967
21. [21] O. Ore, The four color problem. Academic Press, New York (1967). Zbl0149.21101MR216979
22. [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. Zbl0801.68066MR1217999
23. [23] S. V. Ramachandran and J. H. Reif, An optimal parallel algorithm for graph planarity, 30th FOCS (1989) 282-287. 
24. [24] M. O. Rabin, Maximum matching in general graphs through randomization. J. Algorithms 10 (1989) 557-567. Zbl0689.68092MR1022111
25. [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. Zbl0673.05075MR980123
26. [26] V. V. Vazirani, A theory of alternating paths and blossoms for proving correctness of the O(√VE) general graph maximum matching algorithm. Combinatorica 14 (1994) 71-109. Zbl0806.05058MR1273202