On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices

DOI10.1007/978-3-540-77120-3_13zbMATH Open1141.68418OpenAlexW2152376083MaRDI QIDQ5387751FDOQ5387751

Authors Uffe Flarup, Laurent Lyaudet, Pascal Koiran 

Publication date 27 May 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://hal-ens-lyon.archives-ouvertes.fr/ensl-00149062/file/formulas.pdf

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract)
• On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth
• Planarity, determinants, permanents, and (unique) matchings
• Planarity, Determinants, Permanents, and (Unique) Matchings
• On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width

Cites work

• scientific article; zbMATH DE number 3744549 (Why is no real title available?)
• scientific article; zbMATH DE number 475615 (Why is no real title available?)
• scientific article; zbMATH DE number 1859215 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• Characterizing Valiant’s Algebraic Complexity Classes
• Completeness and reduction in algebraic complexity theory
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Parallel algorithms with optimal speedup for bounded treewidth
• The combinatorial approach yields an NC algorithm for computing Pfaffians
• The complexity of computing the permanent
• Two Algorithmic Results for the Traveling Salesman Problem

Cited in

(15)

• On hard instances of non-commutative permanent
• Planarity, Determinants, Permanents, and (Unique) Matchings
• Planarity, determinants, permanents, and (unique) matchings
• Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
• On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract)
• On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth
• Efficient computation of permanents, with applications to boson sampling and random matrices
• On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
• Log-space algorithms for paths and matchings in \(k\)-trees
• An efficient tree decomposition method for permanents and mixed discriminants
• On the expressive power of CNF formulas of bounded tree- and clique-width
• An extended tree-width notion for directed graphs related to the computation of permanents
• Patching colors with tensors
• On hard instances of non-commutative permanent
• An extended tree-width notion for directed graphs related to the computation of permanents

This page was built for publication: On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices

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