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.

Bampis, E. ; Giannakos, A. ; Karzanov, A. ; Manoussakis, Y. ; Milis, I.

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) no. 2, pp. 87-97

MR Zbl

@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},
     pages = {87--97},
     year = {2000},
     publisher = {EDP Sciences},
     volume = {34},
     number = {2},
     mrnumber = {1774303},
     zbl = {0959.05092},
     language = {en},
     url = {https://www.numdam.org/item/ITA_2000__34_2_87_0/}
}

TY  - JOUR
AU  - Bampis, E.
AU  - Giannakos, A.
AU  - Karzanov, A.
AU  - Manoussakis, Y.
AU  - Milis, I.
TI  - Perfect matching in general vs. cubic graphs : a note on the planar and bipartite cases
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2000
SP  - 87
EP  - 97
VL  - 34
IS  - 2
PB  - EDP Sciences
UR  - https://www.numdam.org/item/ITA_2000__34_2_87_0/
LA  - en
ID  - ITA_2000__34_2_87_0
ER  -

%0 Journal Article
%A Bampis, E.
%A Giannakos, A.
%A Karzanov, A.
%A Manoussakis, Y.
%A Milis, I.
%T Perfect matching in general vs. cubic graphs : a note on the planar and bipartite cases
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2000
%P 87-97
%V 34
%N 2
%I EDP Sciences
%U https://www.numdam.org/item/ITA_2000__34_2_87_0/
%G en
%F 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) no. 2, pp. 87-97. https://www.numdam.org/item/ITA_2000__34_2_87_0/

Bibliographie
Cité par

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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