An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents
From MaRDI portal
Publication:3007631
DOI10.1007/978-3-642-20712-9_19zbMath1332.68086OpenAlexW1868658203MaRDI QIDQ3007631
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
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