Deterministically isolating a perfect matching in bipartite planar graphs

DOI10.1007/S00224-009-9204-8MaRDI QIDQ1959397zbMATH OpenOpenAlexFDO

Authors 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

deterministic isolationisolation lemmaNCperfect matchingplanar graphs

Mathematics Subject Classification ID

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) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Deterministically isolating a perfect matching in bipartite planar graphs
• Derandomizing isolation lemma for \(K_{3,3}\)-free and \(K_5\)-free bipartite graphs
• Planar graph perfect matching is in NC
• On the power of isolation in planar graphs
• Bipartite perfect matching is in quasi-NC

Cites work

• A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
• Computing LOGCFL certificates
• Constructing a perfect matching is in random NC
• Directed planar reachability is in unambiguous log-space
• Flow in Planar Graphs with Multiple Sources and Sinks
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• scientific article; zbMATH DE number 3965452 (Why is no real title available?)
• scientific article; zbMATH DE number 4062621 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 6472651 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Matching is as easy as matrix inversion
• Planar and grid graph reachability problems
• Planarity, Determinants, Permanents, and (Unique) Matchings

Cited in

(19)

• Solution to a problem of C. D. Godsil regarding bipartite graphs with unique perfect matching
• On the power of isolation in planar graphs
• Planarity testing revisited
• Space complexity of perfect matching in bounded genus bipartite graphs
• Log-space algorithms for paths and matchings in k-trees
• scientific article; zbMATH DE number 1335883 (Why is no real title available?)
• Space complexity of perfect matching in bounded genus bipartite graphs
• Derandomizing isolation lemma for \(K_{3,3}\)-free and \(K_5\)-free bipartite graphs
• Deterministically isolating a perfect matching in bipartite planar graphs
• Bipartite perfect matching is in quasi-NC
• Isolating a vertex via lattices: polytopes with totally unimodular faces
• NC algorithms for weighted planar perfect matching and related problems
• Planar Maximum Matching: Towards a Parallel Algorithm
• Derandomizing isolation in space-bounded settings
• Isolating a vertex via lattices: polytopes with totally unimodular faces
• A deterministic parallel reduction from weighted matroid intersection search to decision
• Green's theorem and isolation in planar graphs
• Parallel complexity of geometric bipartite matching
• Reachability in graphs with polynomially many surface non-separating cycles is in UL

This page was built for publication: Deterministically isolating a perfect matching in bipartite planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1959397)