서지주요정보
반복적 로컬 검색을 이용한 그래프 색칠 문제에 대한 연구 = Iterated local search for vertex coloring
서명 / 저자 반복적 로컬 검색을 이용한 그래프 색칠 문제에 대한 연구 = Iterated local search for vertex coloring / 조승범.
저자명 조승범 ; Jo, Seung-Bum
발행사항 [대전 : 한국과학기술원, 2011].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8022780

소장위치/청구기호

학술문화관(문화관) 보존서고

MCS 11041

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

Evolutionary algorithm is one of the heuristic algorithms and it has good performance for vertex coloring problem. However, the theoretical foundation of this algorithm is infancy so theoretical analyses are needed. In this thesis, we introduce an iterated local search, one of evolutionary algorithms, which consists of Grundy local search and some mutation operator. And we give theoretical proof that iterated local search can find near-optimal coloring for many graph classes in polynomial expected time.

그래프 색칠 문제에서 휴리스틱 알고리즘의 일종인 진화 알고리즘은 하나 혹은 여러 개의 해를 가지고 여러 연산들을 통해 최적의 해를 찾아 가는 알고리즘으로서 좋은 성능을 보이는 장점이 있지만 이론적인 뒷받침이 부족하다는 약점을 가지고 있다. 본 논문에서는 진화 알고리즘의 한 종류로서 Grundy 로컬 검색과 특정한 mutation 연산으로 이루어져 있는 반복적 로컬 검색 알고리즘을 제시하고 이 알고리즘이 여러 그래프들에 대해서 다항식의 기대 시간 안에 최적에 가까운 해를 준다는 것을 보인다.

서지기타정보

서지기타정보
청구기호 {MCS 11041
형태사항 iii, 24 p. : 삽도 ; 26 cm
언어 한국어
일반주기 저자명의 영문표기 : Seung-Bum Jo
지도교수의 한글표기 : 좌경룡
지도교수의 영문표기 : Kyung-Yong Chwa
학위논문 학위논문(석사) - 한국과학기술원 : 전산학과,
서지주기 참고문헌 : p. 22-23
주제 그래프 색칠 문제
반복적 로컬 검색
Vertex coloring
Iterated local search
QR CODE qr code