Polynomials of bounded tree width (extended abstract)
This paper uses techniques from algorithmic graph theory to solve problems on multivariate polynomials. To such a polynomial, a hypergraph is associated; when the treewidth of this hypergraph is small, several otherwise computationally intractable problems become polynomial time solvable. These problems include the evaluation of multivariate polynomials when the number of monomials is \(O(2^n)\), and problems that deal with questions on feasibility or positivity of systems of polynomials. For the entire collection see [Zbl 0941.00013].
- Farrell polynomials on graphs of bounded tree width
- On trees with the same restricted \(U\)-polynomial and the Prouhet-Tarry-Escott problem
- scientific article; zbMATH DE number 1859215 (Why is no real title available?)
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- My writing
- Polynomial threshold functions of bounded tree-width: some explainability and complexity aspects
This page was built for publication: Polynomials of bounded tree width (extended abstract)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4502591)
