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

DOI10.4230/LIPICS.MFCS.2020.43MaRDI QIDQ5089210zbMATH OpenOpenAlexFDO

Authors Chetan Gupta, Vimal Raj Sharma, 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

• scientific article; zbMATH DE number 3698383 (Why is no real title available?)
• Bipartite perfect matching is in quasi-NC
• Compressed Decision Problems in Hyperbolic Groups.
• Constant Depth Reducibility
• Derandomizing isolation lemma for \(K_{3,3}\)-free and \(K_5\)-free bipartite graphs
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Making Nondeterminism Unambiguous
• Matching is as easy as matrix inversion
• Paths, Trees, and Flowers
• Space complexity of perfect matching in bounded genus bipartite graphs
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• The Polynomially Bounded Perfect Matching Problem Is in NC 2
• Trading determinism for time in space bounded computations
• Undirected connectivity in log-space

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5089210)