%0 Journal Article
%T Randomized Algorithm For 3-Set Splitting Problem and it's Markovian Model
%J Journal of Algorithms and Computation
%I University of Tehran
%Z 2476-2776
%A Heidari, Mahdi
%A Golshani, Ali
%A Moazzami, D.
%A Moeini, Ali
%D 2016
%\ 04/01/2016
%V 47
%N 1
%P 79-92
%! Randomized Algorithm For 3-Set Splitting Problem and it's Markovian Model
%K NP-complete problem
%K set splitting problem
%K SAT problem
%K Markov chain
%R 10.22059/jac.2016.7944
%X In this paper we restrict every set splitting problem to the special case in which every set has just three elements. This restricted version is also NP-complete. Then, we introduce a general conversion from any set splitting problem to 3-set splitting. Then we introduce a randomize algorithm, and we use Markov chain model for run time complexity analysis of this algorithm. In the last section of this paper we introduce "Fast Split" algorithm.
%U https://jac.ut.ac.ir/article_7944_cf76fdb4b0ab6812faebfef5f611d4d6.pdf