Space complexity of perfect matching in bounded genus bipartite graphs

DOI10.1016/J.JCSS.2011.11.002MaRDI QIDQ439936zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Space complexity of perfect matching in bounded genus bipartite graphs
• Improved bounds for bipartite matching on surfaces
• Deterministically isolating a perfect matching in bipartite planar graphs
• On the Bipartite Unique Perfect Matching Problem
• Space-efficient counting in graphs on surfaces

Cites work

• scientific article; zbMATH DE number 49719 (Why is no real title available?)
• Boolean complexity classes vs. their arithmetic analogs
• Computational Complexity
• Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
• Deterministically isolating a perfect matching in bipartite planar graphs
• Directed planar reachability is in unambiguous log-space
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
• Flow in Planar Graphs with Multiple Sources and Sinks
• Graphs on surfaces
• Green's theorem and isolation in planar graphs
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
• Making Nondeterminism Unambiguous
• Matching is as easy as matrix inversion
• Planar and grid graph reachability problems
• Some perfect matchings and perfect half-integral matchings in NC
• The graph genus problem is NP-complete
• Undirected connectivity in log-space

Cited in

(11)

• Space-efficient counting in graphs on surfaces
• In-place algorithms for computing a largest clique in geometric intersection graphs
• Space complexity of perfect matching in bounded genus bipartite graphs
• scientific article; zbMATH DE number 4001498 (Why is no real title available?)
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
• Derandomizing isolation in space-bounded settings
• Planar Maximum Matching: Towards a Parallel Algorithm
• Embedding and canonizing graphs of bounded genus in logspace
• Compressed Decision Problems in Hyperbolic Groups.
• On the Bipartite Unique Perfect Matching Problem

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)