Planar Maximum Matching: Towards a Parallel Algorithm
From MaRDI portal
Publication:5091011
DOI10.4230/LIPIcs.ISAAC.2018.21OpenAlexW2907702044MaRDI QIDQ5091011
Raghav Kulkarni, Anish Mukherjee, Ashish Kumar, Samir Datta
Publication date: 21 July 2022
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9969/pdf/LIPIcs-ISAAC-2018-21.pdf/
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sparsity. Graphs, structures, and algorithms
- Space complexity of perfect matching in bounded genus bipartite graphs
- Counting the number of perfect matchings in \(K_{5}\)-free graphs
- Approximating weighted matchings in parallel
- Matching theory
- Matching is as easy as matrix inversion
- On the theory of Pfaffian orientations. II: \(T\)-joins, \(k\)-cuts, and duality of enumeration
- The combinatorial approach yields an NC algorithm for computing Pfaffians
- Deterministically isolating a perfect matching in bipartite planar graphs
- Isolation, matching, and counting uniform and nonuniform upper bounds
- On the possibilities and limitations of pseudodeterministic algorithms
- A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
- Derandomizing Isolation Lemma for K3,3-free and K5-free Bipartite Graphs
- Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs
- Flow in Planar Graphs with Multiple Sources and Sinks
- Pseudodeterministic constructions in subexponential time
- Pseudo-deterministic Proofs
- NC Algorithms for Weighted Planar Perfect Matching and Related Problems
- Bipartite Perfect Matching in Pseudo-Deterministic NC
- Planar Graph Perfect Matching Is in NC
- Reproducibility and Pseudo-Determinism in Log-Space
- Paths, Trees, and Flowers
- Bipartite perfect matching is in quasi-NC
- Planarity, Determinants, Permanents, and (Unique) Matchings
This page was built for publication: Planar Maximum Matching: Towards a Parallel Algorithm
