NC Algorithms for Weighted Planar Perfect Matching and Related Problems
DOI10.4230/LIPIcs.ICALP.2018.97zbMath1499.68287arXiv1709.07869OpenAlexW2963917767MaRDI QIDQ5002779
Publication date: 28 July 2021
Full work available at URL: https://arxiv.org/abs/1709.07869
planar graph\(f\)-factorsNC algorithmsmin-cost flowmaximum-weight matchingmaximum-cardinality matchingmaximum multiple-source multiple-sink flow
Graph theory (including graph drawing) in computer science (68R10) 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) Signed and weighted graphs (05C22) Flows in graphs (05C21)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Green's theorem and isolation in planar graphs
- A combinatoric interpretation of dual variables for weighted matching and \(f\)-factors
- Finding small simple cycle separators for 2-connected planar graphs
- A Las Vegas RNC algorithm for maximum matching
- Constructing a perfect matching is in random NC
- A polynomial algorithm for b-matchings: An alternative approach
- NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
- Improved processor bounds for combinatorial problems in RNC
- Deterministically isolating a perfect matching in bipartite planar graphs
- Processor efficient parallel matching
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Algorithmic Applications of Baur-Strassen’s Theorem
- A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
- The Polynomially Bounded Perfect Matching Problem Is in NC 2
- An O(logn) parallel connectivity algorithm
- Fast Parallel Matrix Inversion Algorithms
- Finding Connected Components in O(log n log log n) Time on the EREW PRAM
- Flow in Planar Graphs with Multiple Sources and Sinks
- Bipartite Perfect Matching in Pseudo-Deterministic NC
- Bipartite perfect matching is in quasi-NC
- Algorithms – ESA 2004
- Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
- Maximum matching and a polyhedron with 0,1-vertices