반복적 로컬 검색을 이용한 그래프 색칠 문제에 대한 연구 = Iterated local search for vertex coloring

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 253
  • Download : 0
그래프 색칠 문제에서 휴리스틱 알고리즘의 일종인 진화 알고리즘은 하나 혹은 여러 개의 해를 가지고 여러 연산들을 통해 최적의 해를 찾아 가는 알고리즘으로서 좋은 성능을 보이는 장점이 있지만 이론적인 뒷받침이 부족하다는 약점을 가지고 있다. 본 논문에서는 진화 알고리즘의 한 종류로서 Grundy 로컬 검색과 특정한 mutation 연산으로 이루어져 있는 반복적 로컬 검색 알고리즘을 제시하고 이 알고리즘이 여러 그래프들에 대해서 다항식의 기대 시간 안에 최적에 가까운 해를 준다는 것을 보인다.
Advisors
좌경룡researcherChwa, Kyung-Yongresearcher
Description
한국과학기술원 : 전산학과,
Publisher
한국과학기술원
Issue Date
2011
Identifier
467926/325007  / 020093515
Language
kor
Description

학위논문(석사) - 한국과학기술원 : 전산학과, 2011.2, [ iii, 24 p. ]

Keywords

그래프 색칠 문제; Vertex coloring; Iterated local search; 반복적 로컬 검색

URI
http://hdl.handle.net/10203/180559
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=467926&flag=dissertation
Appears in Collection
CS-Theses_Master(석사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0