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 (2010)
- Volume: 34, Issue: 2, page 87-97
- ISSN: 0988-3754
Access Full Article
topAbstract
topHow to cite
topReferences
top- H. Alt, N. Blum, K. Mehlhron and M. Paul, Computing a maximum cardinality matching in a bipartite graph in time ). Inform. Process. Lett.37 (1991) 237-240.
- 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).
- 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.
- N. Chiba, T. Nishizeki and N. Saito, Applications of the planar separator theorem. J. Inform. Process.4 (1981) 203-207.
- 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.
- J. Edmonds, Paths, trees and flowers. Canad. J. Math.17 (1965) 449-467.
- T. Feder and R. Motwani, Clique partitions, graph compression and speeding-up algorithms, STOC (1991) 123-133.
- A. Goldberg, S. Plotkin and M. Vaidya, Sublinear time parallel algorithms for matchings and related problems. J. Algorithms14 (1993) 180-213.
- R. Greenlaw and R. Petreschi, Cubic graphs. ACM Computing Surveys27 (1995) 471-495.
- D.Yu. Grigoriev and M. Karpinski, The matching problem for bipartite graphs with polynomially bounded permanents is in NC, FOCS (1987) 166-172.
- T. Hagerup, Optimal parallel algorithms on planar graphs. Inform. and Comput.84 (1990) 71-96.
- M. Karpinski and W. Rytter, Fast parallel algorithms for graph matching problems. Oxford University Press, preprint (to appear).
- G. Lev, N. Pippenger and L. Valiant, A fast parallel algorithm for routing in permutation networks. IEEE Trans. Comput.C-30 (1981) 93-100.
- Y.D. Liang, Finding a maximum matching in a circular-arc graph. Inform. Process. Lett.35 (1993) 185-193.
- L. Lovasz and M. Plummer, Matching Theory. Elsevier Science Publishers (1986).
- S. Micali and V.V. Vazirani, An algorithm for finding maximum matchings in general graphs, FOCS (1980) 17-23.
- G.L. Miller and J. Naor, Flow in planar graphs with multiply sources and sinks, Proc. FOCS (1989) 112-117.
- A. Moitra and R. Jonhson, Parallel algorithms for maximum matching and other problems in interval graphs, TR 88-927. Cornell University (1988).
- K. Mulmuley, U.V. Vazirani and V.V. Vazirani, Matching is as easy as matrix inversion. Combinatorica7 (1987) 105-113.
- T. Nishizeki and N. Chiba, Planar Graphs: Theory and Algorithms. North-Holland (1988).
- O. Ore, The four color problem. Academic Press, New York (1967).
- 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.
- S.V. Ramachandran and J.H. Reif, An optimal parallel algorithm for graph planarity, FOCS (1989) 282-287.
- M.O. Rabin, Maximum matching in general graphs through randomization. J. Algorithms10 (1989) 557-567.
- 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.
- V.V. Vazirani, A theory of alternating paths and blossoms for proving correctness of the general graph maximum matching algorithm. Combinatorica14 (1994) 71-109.