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

Authors: 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; zbMATH DE number 4062621

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 (20)

• Planar graph perfect matching is in NC
• Planar and grid graph reachability problems
• NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs
• 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
• Some perfect matchings and perfect half-integral matchings in NC
• NC algorithms for weighted planar perfect matching and related problems
• Compressed Decision Problems in Hyperbolic Groups.
• Title not available (Why is that?)
• Pfaffian orientations and perfect matchings of scale-free networks
• On the parameterized parallel complexity and the vertex cover problem
• 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)