Planarity, determinants, permanents, and (unique) matchings

DOI10.1145/1714450.1714453MaRDI QIDQ5892182zbMATH OpenOpenAlexFDO

Authors Samir Datta, Raghav Kulkarni, Nutan Limaye, Meena Mahajan

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 graphscounting classesdeterminantperfect matchingpermanentplanarity

Mathematics Subject Classification ID

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) Determinants, permanents, traces, other special matrix functions (15A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Planarity, Determinants, Permanents, and (Unique) Matchings
• Undirected determinant and its complexity
• Space-efficient counting in graphs on surfaces
• On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
• Deterministically isolating a perfect matching in bipartite planar graphs

Cited in

(8)

• On hard instances of non-commutative permanent
• On hard instances of non-commutative permanent
• Bounded treewidth and space-efficient linear algebra
• The complexity of generalized domino tilings
• Planar Maximum Matching: Towards a Parallel Algorithm
• On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
• Planarity, Determinants, Permanents, and (Unique) Matchings
• Space-efficient counting in graphs on surfaces

This page was built for publication: Planarity, determinants, permanents, and (unique) matchings

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