An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents

DOI10.1007/978-3-642-20712-9_19zbMath1332.68086OpenAlexW1868658203MaRDI QIDQ3007631

Klaus Meer

Publication date: 17 June 2011

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20712-9_19

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Directed graphs (digraphs), tournaments (05C20)

Related Items

Efficient computation of permanents, with applications to boson sampling and random matrices ⋮ Unnamed Item ⋮ An efficient tree decomposition method for permanents and mixed discriminants

Cites Work

• The complexity of computing the permanent
• On the expressive power of CNF formulas of bounded tree- and clique-width
• Directed tree-width
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Complexity of Finding Embeddings in a k-Tree
• Two Algorithmic Results for the Traveling Salesman Problem
• On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
• Logic for Programming, Artificial Intelligence, and Reasoning
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic