Ohad Shamir, Sivan Sabato, et al.
Theoretical Computer Science
The problem of finding a minimum dominating set in a tournament can be solved in nO(log n) time. It is shown that if this problem has a polynomial-time algorithm, then for every constant C, there is also a polynomial-time algorithm for the satisfiability problem of boolean formulas in conjunctive normal form with m clauses and C log2 m variables. On the other hand, the problem can be reduced in polynomial time to a general satisfiability problem of length L with O(log2 L) variables. Another relation between the satisfiability problem and the minimum dominating set in a tournament says that the former can be solved in 2O(√v) nK time (where v is the number of variables, n is the length of the formula, and K is a constant) if and only if the latter has a polynomial-time algorithm. © 1988.
Ohad Shamir, Sivan Sabato, et al.
Theoretical Computer Science
N.K. Ratha, A.K. Jain, et al.
Workshop CAMP 2000
Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics
Qing Li, Zhigang Deng, et al.
IEEE T-MI