The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell).
Libor BartoMarcin KozikTodd NivenPublished in: SIAM J. Comput. (2009)
Keyphrases
- constraint satisfaction problems
- positive and negative
- multiple sources
- constraint satisfaction
- directed graph
- decomposition methods
- information sources
- covariance matrices
- constraint networks
- arc consistency
- constraint programming
- sensor networks
- data sources
- positively correlated
- tree decomposition
- search engine
- arc consistency algorithm
- equivalence classes
- markov models
- np complete
- np hard
- hidden markov models