NC Algorithms for Weighted Planar Perfect Matching and Related Problems

DOI10.4230/LIPIcs.ICALP.2018.97zbMath1499.68287arXiv1709.07869OpenAlexW2963917767MaRDI QIDQ5002779

Piotr Sankowski

Publication date: 28 July 2021

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

zbMATH Keywords

planar graph\(f\)-factorsNC algorithmsmin-cost flowmaximum-weight matchingmaximum-cardinality matchingmaximum multiple-source multiple-sink flow

Mathematics Subject Classification ID

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

On the parallel complexity of constrained read-once refutations in UTVPI constraint systems, Polyhedral techniques in combinatorial optimization: matchings and tours, Min-Cost Flow in Unit-Capacity Planar Graphs, Planar Maximum Matching: Towards a Parallel Algorithm, NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs

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