Maximum Bipartite Subgraph 문제를 위한 GRASP + Tabu Search 알고리즘 연구

Maximum Bipartite Subgraph 문제를 위한 GRASP + Tabu Search 알고리즘 연구

ㆍ 저자명: 한근희,김찬수,Han. Keunhee,Kim. Chansoo
ㆍ 간행물명: 정보처리학회논문지. KIPS transactions on software and data engineering. 소프트웨어 및 데이터 공학
ㆍ 권/호정보: 2014년|3권 3호|pp.119-124 (6 pages)
ㆍ 발행정보: 한국정보처리학회
ㆍ 파일정보: 정기간행물|
PDF텍스트
ㆍ 주제분야: 기타

이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.

서지반출

기타언어초록

G = (V, E) 를 그래프라 하자. Maximum Bipartite Subgraph 문제는 주어진 그래프 G로부터 최소 개수의 간선을 제거함으로써 G 를 이분그래프로 변환시키는 문제이며 결합 최적화 문제들 중 대표적인 문제들 중의 하나로 알려 져 있다. 본 문제는 NP-complete 계열에 포함되는 문제로서 본 연구에서는 Tabu Search 및 GRASP 등을 조합한 새로운 메타휴리스틱 알고리즘을 제시하고자 한다.

기타언어초록

Let G = (V, E) be a graph. Maximum Bipartite Subgraph Problem is to convert a graph G into a bipartite graph by removing minimum number of edges. This problem belongs to NP-complete; hence, in this research, we are suggesting a new metaheuristic algorithm which combines Tabu search and GRASP.

키워드

그래프 이분 그래프 Maximum Bipartite Subgraph 문제 Graph Bipartite Graph Maximum Bipartite Subgraph Problem Tabu Search GRASP

다운URL