본문 바로가기
  • Home

A Marriage Problem Algorithm Based on Duplicated Sum of Inter-Preference Moving Method

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2015, 20(5), pp.107-112
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Sang-Un, Lee 1

1강릉원주대학교

Accredited

ABSTRACT

This paper proposes a simplified algorithm devised to obtain optimal solution to the marriage problem. In solving this problem, the most widely resorted to is the Gale-Shapley algorithm with the time complexity of O(│V│2│E│)The proposed algorithm on the other hand firstly constructs a Pij matrix of inter-preference sum both sexes’ preference over the opposite sex. Secondly, it selects minPi from each row to establish│P.j│≥ 2, j∈S ,│P.j │= 1 , j∈H ,│P.j │= 0 , j∈T. Finally, it shifts min{minPST,PSH+PHT} for minPST of S→T and PSH+PHT ,PHT<minPST of S→H, H→T . The proposed algorithm has not only improved the Gale-Shapley’s algorithm’s complexity of O(│V│2│E│)to O(│V│2) but also proved its extendable use on unbalanced marriage problems.

Citation status

* References for papers published after 2022 are currently being built.