Planarity, Determinants, Permanents, and (Unique) Matchings

DOI10.1145/1714450.1714453zbMath1322.05088OpenAlexW2131343967MaRDI QIDQ5892182

Raghav Kulkarni, Nutan Limaye, Meena Mahajan, Samir Datta

Publication date: 24 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1714450.1714453

zbMATH Keywords

bipartite graphsplanaritydeterminantpermanentperfect matchingcounting classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15) Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Bounded Treewidth and Space-Efficient Linear Algebra ⋮ The complexity of generalized domino tilings ⋮ On Hard Instances of Non-Commutative Permanent ⋮ On hard instances of non-commutative permanent ⋮ Planar Maximum Matching: Towards a Parallel Algorithm

This page was built for publication: Planarity, Determinants, Permanents, and (Unique) Matchings