Undirected determinant and its complexity

DOI10.1007/s00373-023-02671-7zbMath1519.05152arXiv2108.13090OpenAlexW4383343769MaRDI QIDQ6166664

Diana Dziewa-Dawidczyk, Adam J. Przeździecki

Publication date: 3 August 2023

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2108.13090

zbMATH Keywords

computational complexityplanar graphsdeterminantPfaffian orientationenumerative combinatoricsundirected permanent

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) 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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Expressiveness of matchgates.
• The statistics of dimers on a lattice
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• The complexity of the fermionant, and immanants of constant width
• Holographic Algorithms
• Determinant versus Permanent: Salvation via Generalization?
• Dimer problem in statistical mechanics-an exact result
• Almost settling the hardness of noncommutative determinant

This page was built for publication: Undirected determinant and its complexity