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

DOI10.1145/335305.335346zbMath1296.05187OpenAlexW2127932013MaRDI QIDQ3192003

Meena Mahajan, Kasturi R. 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

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

The combinatorial approach yields an NC algorithm for computing Pfaffians ⋮ NC Algorithms for Weighted Planar Perfect Matching and Related Problems ⋮ On the Parameterized Parallel Complexity and the Vertex Cover Problem ⋮ Deterministically isolating a perfect matching in bipartite planar graphs ⋮ Maximum matchings in scale-free networks with identical degree distribution ⋮ Pfaffian orientations and perfect matchings of scale-free networks ⋮ Planar and grid graph reachability problems ⋮ Compressed Decision Problems in Hyperbolic Groups. ⋮ Planar Maximum Matching: Towards a Parallel Algorithm ⋮ NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs ⋮ Bipartite Perfect Matching is in Quasi-NC

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