On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth/cliquewidth

DOI10.1007/s00224-009-9241-3zbMath1197.68047arXiv0801.3408OpenAlexW1988819200MaRDI QIDQ987381

Uffe Flarup, Laurent Lyaudet

Publication date: 13 August 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

Hamiltonianpermanentalgebraic complexityperfect matchingcycle coverValiant's modeltopological pathwidthweighted cliquewidth

Mathematics Subject Classification ID

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) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The rank-width of edge-coloured graphs ⋮ Small space analogues of Valiant's classes and the limitations of skew formulas ⋮ $\mathbb F$ -Rank-Width of (Edge-Colored) Graphs ⋮ On Hard Instances of Non-Commutative Permanent ⋮ On hard instances of non-commutative permanent

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• A partial k-arboretum of graphs with bounded treewidth
• \(k\)-NLC graphs and polynomial algorithms
• Upper bounds to the clique width of graphs
• The statistics of dimers on a lattice
• Statistical Mechanics of Dimers on a Plane Lattice
• Compact Forbidden-Set Routing
• Computing Algebraic Formulas Using a Constant Number of Registers
• On the Relationship Between Clique-Width and Treewidth
• Dimer problem in statistical mechanics-an exact result
• On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
• Characterizing Valiant’s Algebraic Complexity Classes
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic