Space complexity of perfect matching in bounded genus bipartite graphs
From MaRDI portal
Publication:439936
DOI10.1016/j.jcss.2011.11.002zbMath1253.68168MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C10: Planar graphs; geometric and topological aspects of graph theory
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
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, In-place algorithms for computing a largest clique in geometric intersection graphs
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
