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

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

Laurent Lyaudet, Uffe Flarup

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

Hamiltonian; permanent; algebraic complexity; perfect matching; cycle cover; Valiant's model; topological pathwidth; weighted cliquewidth

Mathematics Subject Classification ID

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Small space analogues of Valiant's classes and the limitations of skew formulas, The rank-width of edge-coloured graphs, $\mathbb F$ -Rank-Width of (Edge-Colored) Graphs

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