• Home
  • Browse
    • Current Issue
    • By Issue
    • By Author
    • By Subject
    • Author Index
    • Keyword Index
  • Submit Paper
  • Journal Info
    • About Journal
    • Aims and Scope
    • Editorial Board
    • Advisory Editorial Board
    • Editorial Staff
    • Publication Ethics
    • Indexing Databases
    • Related Links
    • FAQ
    • Peer Review Process
    • News
  • Guide for Authors
  • Reviewers
  • Contact Us
 
  • Login
  • Register
Home Article Info
  • Save Records
  • |
  • Printable Version
  • |
  • Recommend
  • |
  • Export Citation Export to
    RIS EndNote
Journal of Algorithms and Computation
Articles in Press
Current Issue
Journal Archive
Volume Volume 49 (2017)
Volume Volume 48 (2016)
Volume Volume 47 (2016)
Issue Issue 1
Volume Volume 46 (2015)
Volume Volume 45 (2014)
Volume Volume 44 (2013)
Volume Volume 43 (2009)
Volume Volume 42 (2008)
Volume Volume 41 (2007)

Randomized Algorithm For 3-Set Splitting Problem and it's Markovian Model

Article 8, Volume 47, Issue 1, Spring 2016, Page 79-92  XML PDF (393 K)
Document Type: Research Paper
Authors
1 Mahdi Heidari ; 1 Ali Golshani; 2 D. Moazzami; 2 Ali Moeini
1Department of Algorithms and Computation, University of Tehran
2University of Tehran, College of Engineering, Faculty of Enginering Science
Abstract
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.
Keywords
NP-complete problem; set splitting problem; SAT problem; Markov chain
Statistics
Article View: 755
PDF Download: 795
Home | Glossary | News | Aims and Scope | Sitemap
Top Top

open access Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

 
© 2018 - Journal Management System. Created by sinaweb.