Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases
From MaRDI portal
Publication:4508634
DOI10.1051/ita:2000108zbMath0959.05092OpenAlexW2064728122MaRDI QIDQ4508634
Alexander V. Karzanov, Ioannis Milis, Aristotelis Giannakos, Evripidis Bampis, Yannis Manoussakis
Publication date: 26 April 2001
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/222060
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal parallel algorithms on planar graphs
- Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
- Matching is as easy as matrix inversion
- NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
- Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem
- Finding a maximum matching in a circular-arc graph
- Planar graphs: Theory and algorithms
- A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
- Clique partitions, graph compression and speeding-up algorithms
- Maximum matchings in general graphs through randomization
- Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
- A fast parallel algorithm for routing in permutation networks
- Sublinear-Time Parallel Algorithms for Matching and Related Problems
- Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases
- Paths, Trees, and Flowers
This page was built for publication: Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases
