Planar Graph Perfect Matching Is in NC

DOI10.1145/3397504zbMath1491.68131arXiv1709.07822OpenAlexW3033132981MaRDI QIDQ5133976

Vijay V. Vazirani, Nima Anari

Publication date: 11 November 2020

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1709.07822

zbMATH Keywords

parallel algorithmPfaffianplanar graphperfect matchingTutte matrix

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Parallel algorithms in computer science (68W10)

Related Items (8)

On the parallel complexity of constrained read-once refutations in UTVPI constraint systems ⋮ Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ Speeding up the Gomory-Hu parallel cut tree algorithm with efficient graph contractions ⋮ Unnamed Item ⋮ 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 ⋮ Unnamed Item

This page was built for publication: Planar Graph Perfect Matching Is in NC