Fully polynomial-time parameterized computations for graphs and matrices of low treewidth.
Fedor V. FominDaniel LokshtanovMichal PilipczukSaket SaurabhMarcin WrochnaPublished in: SODA (2017)
Keyphrases
- bounded treewidth
- np complete
- decision problems
- conjunctive queries
- graph isomorphism
- special case
- upper bound
- singular value decomposition
- graph theoretic
- polynomial time complexity
- computational complexity
- np hard
- boolean functions
- graph matching
- graph structure
- relational learning
- tractable classes
- tree decompositions
- pairwise comparison
- spanning tree
- graph databases
- graph theory
- low rank
- directed graph