Leo Liberti, James Ostrowski
Journal of Global Optimization
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.
Leo Liberti, James Ostrowski
Journal of Global Optimization
Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
Fan Jing Meng, Ying Huang, et al.
ICEBE 2007
N.K. Ratha, A.K. Jain, et al.
Workshop CAMP 2000