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

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

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2000)

  • Volume: 34, Issue: 2, page 87-97
  • ISSN: 0988-3754

How to cite

top

Bampis, E., et al. "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 34.2 (2000): 87-97. <http://eudml.org/doc/92629>.

@article{Bampis2000,
author = {Bampis, E., Giannakos, A., Karzanov, A., Manoussakis, Y., Milis, I.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {perfect matching; planar graphs; cubic graphs},
language = {eng},
number = {2},
pages = {87-97},
publisher = {EDP-Sciences},
title = {Perfect matching in general vs. cubic graphs : a note on the planar and bipartite cases},
url = {http://eudml.org/doc/92629},
volume = {34},
year = {2000},
}

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
PB - EDP-Sciences
VL - 34
IS - 2
SP - 87
EP - 97
LA - eng
KW - perfect matching; planar graphs; cubic graphs
UR - http://eudml.org/doc/92629
ER -

References

top
  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

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.