A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)

DOI10.1145/335305.335346zbMATH Open1296.05187OpenAlexW2127932013MaRDI QIDQ3192003FDOQ3192003

Meena Mahajan, Kasturi Varadarajan

Publication date: 26 September 2014

Published in: Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/335305.335346

Recommendations

• Some perfect matchings and perfect half-integral matchings in NC
• Planar graph perfect matching is in NC
• Algorithms – ESA 2004
• A New NC-Algorithm for Finding a Perfect Matching in d-Regular Bipartite Graphs When d Is Small
• scientific article

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10)

Cited In (18)

• Planar and grid graph reachability problems
• On the Parameterized Parallel Complexity and the Vertex Cover Problem
• NC Algorithms for Weighted Planar Perfect Matching and Related Problems
• Deterministically isolating a perfect matching in bipartite planar graphs
• Bipartite Perfect Matching is in Quasi-NC
• Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases
• Planar Maximum Matching: Towards a Parallel Algorithm
• The combinatorial approach yields an NC algorithm for computing Pfaffians
• The Polynomially Bounded Perfect Matching Problem Is in NC 2
• Compressed Decision Problems in Hyperbolic Groups.
• NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs
• Title not available (Why is that?)
• Pfaffian orientations and perfect matchings of scale-free networks
• Title not available (Why is that?)
• NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
• A New NC-Algorithm for Finding a Perfect Matching in d-Regular Bipartite Graphs When d Is Small
• Algorithms – ESA 2004
• Maximum matchings in scale-free networks with identical degree distribution

This page was built for publication: A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192003)