Space complexity of perfect matching in bounded genus bipartite graphs

DOI10.1016/j.jcss.2011.11.002zbMath1253.68168OpenAlexW1496024985MaRDI QIDQ439936

Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran, Samir Datta

Publication date: 17 August 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.11.002

zbMATH Keywords

perfect matchingspace complexitytopological graph theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

In-place algorithms for computing a largest clique in geometric intersection graphs ⋮ Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs ⋮ Compressed Decision Problems in Hyperbolic Groups. ⋮ Planar Maximum Matching: Towards a Parallel Algorithm ⋮ Derandomizing Isolation in Space-Bounded Settings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Green's theorem and isolation in planar graphs
• Planar and grid graph reachability problems
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
• Matching is as easy as matrix inversion
• Deterministically isolating a perfect matching in bipartite planar graphs
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Directed Planar Reachability Is in Unambiguous Log-Space
• Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
• The graph genus problem is NP-complete
• Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
• Undirected connectivity in log-space
• Flow in Planar Graphs with Multiple Sources and Sinks
• Boolean complexity classes vs. their arithmetic analogs
• Making Nondeterminism Unambiguous
• Computational Complexity

This page was built for publication: Space complexity of perfect matching in bounded genus bipartite graphs