Deterministically isolating a perfect matching in bipartite planar graphs

DOI10.1007/s00224-009-9204-8zbMath1206.68231OpenAlexW1978026115MaRDI QIDQ1959397

Samir Datta, Raghav Kulkarni, Sambuddha Roy

Publication date: 6 October 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2008/1346/

zbMATH Keywords

planar graphsperfect matchingNCisolation lemmadeterministic isolation

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) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

NC Algorithms for Weighted Planar Perfect Matching and Related Problems ⋮ Log-space algorithms for paths and matchings in \(k\)-trees ⋮ A deterministic parallel reduction from weighted matroid intersection search to decision ⋮ Unnamed Item ⋮ Space complexity of perfect matching in bounded genus bipartite graphs ⋮ Planarity Testing Revisited ⋮ Green's theorem and isolation in planar graphs ⋮ Planar Maximum Matching: Towards a Parallel Algorithm ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ Bipartite Perfect Matching is in Quasi-NC ⋮ Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Planar and grid graph reachability problems
• Matching is as easy as matrix inversion
• Constructing a perfect matching is in random NC
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Directed Planar Reachability Is in Unambiguous Log-Space
• A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
• Flow in Planar Graphs with Multiple Sources and Sinks
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Planarity, Determinants, Permanents, and (Unique) Matchings
• Computing LOGCFL certificates