Space complexity of perfect matching in bounded genus bipartite graphs
DOI10.1016/J.JCSS.2011.11.002zbMATH Open1253.68168OpenAlexW1496024985MaRDI QIDQ439936FDOQ439936
Authors: Samir Datta, Raghav Kulkarni, Raghunath Tewari, N. V. Vinodchandran 
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
Recommendations
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)
Cites Work
- Computational Complexity
- Graphs on surfaces
- Undirected connectivity in log-space
- Title not available (Why is that?)
- The graph genus problem is NP-complete
- Matching is as easy as matrix inversion
- Flow in Planar Graphs with Multiple Sources and Sinks
- Boolean complexity classes vs. their arithmetic analogs
- Making Nondeterminism Unambiguous
- Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
- Deterministically isolating a perfect matching in bipartite planar graphs
- Planar and grid graph reachability problems
- Finding shortest non-separating and non-contractible cycles for topologically embedded 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
- Some perfect matchings and perfect half-integral matchings in NC
- Green's theorem and isolation in planar graphs
Cited In (11)
- Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
- Embedding and canonizing graphs of bounded genus in logspace
- Derandomizing isolation in space-bounded settings
- In-place algorithms for computing a largest clique in geometric intersection graphs
- Title not available (Why is that?)
- Planar Maximum Matching: Towards a Parallel Algorithm
- Space-efficient counting in graphs on surfaces
- On the Bipartite Unique Perfect Matching Problem
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Space complexity of perfect matching in bounded genus bipartite graphs
- Compressed Decision Problems in Hyperbolic Groups.
This page was built for publication: Space complexity of perfect matching in bounded genus bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q439936)
