On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
From MaRDI portal
Publication:5387751
DOI10.1007/978-3-540-77120-3_13zbMath1141.68418OpenAlexW2152376083MaRDI QIDQ5387751
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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (13)
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 ⋮ 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 (Extended Abstract) ⋮ An efficient tree decomposition method for permanents and mixed discriminants ⋮ An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents ⋮ Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems ⋮ An extended tree-width notion for directed graphs related to the computation of permanents ⋮ Unnamed Item ⋮ On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth ⋮ On Hard Instances of Non-Commutative Permanent ⋮ On hard instances of non-commutative permanent
Cites Work
- The complexity of computing the permanent
- Completeness and reduction in algebraic complexity theory
- The combinatorial approach yields an NC algorithm for computing Pfaffians
- Parallel algorithms with optimal speedup for bounded treewidth
- Two Algorithmic Results for the Traveling Salesman Problem
- Characterizing Valiant’s Algebraic Complexity Classes
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
