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
Laurent Lyaudet, Uffe Flarup, 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
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)
Cites Work
- Title not available (Why is that?)
- The complexity of computing the permanent
- Two Algorithmic Results for the Traveling Salesman Problem
- Completeness and reduction in algebraic complexity theory
- Parallel algorithms with optimal speedup for bounded treewidth
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Title not available (Why is that?)
- The combinatorial approach yields an NC algorithm for computing Pfaffians
- Characterizing Valiant’s Algebraic Complexity Classes
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (13)
- On the expressive power of CNF formulas of bounded tree- and clique-width
- 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
- An extended tree-width notion for directed graphs related to the computation of permanents
- On Hard Instances of Non-Commutative Permanent
- An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents
- Title not available (Why is that?)
- On hard instances of non-commutative permanent
- On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract)
- Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
- Log-space algorithms for paths and matchings in \(k\)-trees
- An efficient tree decomposition method for permanents and mixed discriminants
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 👍 👎
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)
