Earticle

초록

영어

The wedding seating problem(WSP) is to finding a minimum loss of guest relations(sit together preference) with restricted seats of a table for complex guest relation network. The WSP is NP-hard because of the algorithm that can be find the optimal solution within polynomial-time is unknown yet. Therefore we can’t solve the WSP not computer-assisted programming but by hand. This paper suggests min-cut rule theory that the two guests with maximum preference can’t separate in other two tables because this is not obtains minimum loss of preference. As a result of various experimental, this algorithm obtains proper seating chart meet to the seats of a table constraints.

한국어

복잡한 관계(동석 선호도)망을 갖고 있는 결혼 연회장에 참석하는 하객들에 대해 테이블 당 좌석 수가 한정되어 있는 경우, 최소의 관계 손실을 갖도록 좌석을 배정하는 문제를 결혼 연회장 좌석 배정 문제(WSP)라 한다. 이 문제는 다항시 간을 해를 구하는 방법이 알려져 있지 않아 NP-난제로 분류되어 있으며, 컴퓨터 프로그램 도움 없이 손으로 다항시간으로 해를 구하는 알고리즘은 알려져 있지 않다. 본 논문에서는 최대 관계를 갖는 두 하객을 분리하면 최소 절단(관계 손실 최소 화)을 얻지 못한다는 이론에 기반하여 최소절단 값을 갖도록 하객 관계망을 분할하는 규칙을 적용하였다. 제안된 알고리즘을 다양한 실험 데이터에 적용한 결과 테이블 당 좌석 수 제약조건에 맞는 좌석 배정표를 쉽게 얻을 수 있었다.

목차

요약
Abstract
Ⅰ. 서론
Ⅱ. 관련 연구와 문제점
Ⅲ. 최소절단 좌석 배정 알고리즘
Ⅳ. 알고리즘 적용성 평가
Ⅴ. 결론
References

키워드

저자

• 이상운 [ Sang-Un, Lee | 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과 ] Corresponding Author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380