Perfect matching in general vs. cubic graphs : a note on the planar and bipartite cases
Bampis, E. ; Giannakos, A. ; Karzanov, A. ; Manoussakis, Y. ; Milis, I.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000), p. 87-97 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 2000-01-01
@article{ITA_2000__34_2_87_0,
     author = {Bampis, E. and Giannakos, A. and Karzanov, A. and Manoussakis, Y. and Milis, I.},
     title = {Perfect matching in general vs. cubic graphs : a note on the planar and bipartite cases},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {34},
     year = {2000},
     pages = {87-97},
     mrnumber = {1774303},
     zbl = {0959.05092},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2000__34_2_87_0}
}

Bampis, E.; Giannakos, A.; Karzanov, A.; Manoussakis, Y.; Milis, I. Perfect matching in general vs. cubic graphs : a note on the planar and bipartite cases. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) pp. 87-97. http://gdmltest.u-ga.fr/item/ITA_2000__34_2_87_0/

[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. | MR 1095712 | Zbl 0714.68036

[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).

[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. | MR 925193 | Zbl 0637.68038

[4] N. Chiba, T. Nishizeki and N. Saito, Applications of the planar separator theorem. J. Inform. Process. 4 (1981) 203-207. | MR 652015 | Zbl 0477.68069

[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. | MR 1161106 | Zbl 0743.68072

[6] J. Edmonds, Paths, trees and flowers Canad. J. Math. 17 (1965) 449-467. | MR 177907 | Zbl 0132.20903

[7] T. Feder and R. Motwani, Clique partitions, graph compression and speeding-up algorithms, 23th STOC (1991) 123-133.

[8] A. Goldberg, S. Plotkin and M. Vaidya, Sublinear time parallel algorithms for matchings and related problems. J. Algorithms 14 (1993) 180-213. | MR 1201924 | Zbl 0769.68034

[9] R. Greenlaw and R. Petreschi, Cubic graphs. ACM Computing Surveys 27 (1995) 471-495.

[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] T. Hagerup, Optimal parallel algorithms on planar graphs. Inform. and Comput 84 (1990) 71-96. | MR 1032155 | Zbl 0689.68056

[12] M. Karpinski and W. Rytter, Fast parallel algorithms for graph matching problems. Oxford University Press, preprint (to appear). | MR 1627822 | Zbl 0895.05050

[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. | MR 605719 | Zbl 0455.94047

[14] Y. D. Liang, Finding a maximum matching in a circular-arc graph. Inform. Process. Lett. 35 (1993) 185-193. | MR 1211528 | Zbl 0768.68159

[15] L. Lovasz and M. Plummer, Matching Theory. Elsevier Science Publishers (1986). | MR 859549 | Zbl 0618.05001

[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] G. L. Miller and J. Naor, Flow in planar graphs wüh multiply sources and sinks, Proc. 30th 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. Combinatorica 7 (1987) 105-113. | MR 905157 | Zbl 0632.68041

[20] T. Nishizeki and N. Chiba, Planar Graphs: Theory and Algorithms. North-Holland (1988). | MR 941967 | Zbl 0647.05001

[21] O. Ore, The four color problem. Academic Press, New York (1967). | MR 216979 | Zbl 0149.21101

[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. | MR 1217999 | Zbl 0801.68066

[23] S. V. Ramachandran and J. H. Reif, An optimal parallel algorithm for graph planarity, 30th FOCS (1989) 282-287.

[24] M. O. Rabin, Maximum matching in general graphs through randomization. J. Algorithms 10 (1989) 557-567. | MR 1022111 | Zbl 0689.68092

[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. | MR 980123 | Zbl 0673.05075

[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. | MR 1273202 | Zbl 0806.05058