Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs

DOI10.4230/LIPIcs.MFCS.2020.43OpenAlexW3082057387MaRDI QIDQ5089210

Vimal Raj Sharma, Chetan Gupta, Raghunath Tewari

Publication date: 18 July 2022

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12709/pdf/LIPIcs-MFCS-2020-43.pdf/

zbMATH Keywords

high genuslogspace computationmatching isolation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Space complexity of perfect matching in bounded genus bipartite graphs
• Matching is as easy as matrix inversion
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Constant Depth Reducibility
• The Polynomially Bounded Perfect Matching Problem Is in NC 2
• Undirected connectivity in log-space
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Derandomizing Isolation Lemma for K3,3-free and K5-free Bipartite Graphs
• Making Nondeterminism Unambiguous
• Compressed Decision Problems in Hyperbolic Groups.
• Paths, Trees, and Flowers
• Bipartite perfect matching is in quasi-NC

This page was built for publication: Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs