논문KCI 등재
Maximum Bipartite Subgraph 문제를 위한 GRASP + Tabu Search 알고리즘 연구
Study for the Maximum Bipartite Subgraph Problem Using GRASP + Tabu Search
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
주제분류컴퓨터학
초록
G = (V, E) 를 그래프라 하자. Maximum Bipartite Subgraph 문제는 주어진 그래프 G로부터 최소 개수의 간선을 제거함으로써 G 를이분그래프로 변환시키는 문제이며 결합 최적화 문제들 중 대표적인 문제들 중의 하나로 알려 져 있다. 본 문제는 NP-complete 계열에 포함되는 문제로서 본 연구에서는 Tabu Search 및 GRASP 등을 조합한 새로운 메타휴리스틱 알고리즘을 제시하고자 한다.
Abstract
Let G = (V, E) be a graph. Maximum Bipartite Subgraph Problem is to convert a graph G into a bipartite graph by removingminimum number of edges. This problem belongs to NP-complete; hence, in this research, we are suggesting a new metaheuristicalgorithm which combines Tabu search and GRASP.
참고문헌 (12)
- R. M. Karp, "Complexity of Computer Computations", pp.85~104 (1972), Plenum
- NP-completeness of several arrangement problems, "S. Even", Dept. Computer Science, Technion, ~, pp.Tech. Rep. 43, 1975 (1975)
- M. R. Garey, "Some simplified NP-complete graph problems", Theoretical Computer Science, 1, pp.237~267 (1976)
- J. A. Bondy, "Largest bipartite subgraph in triangle-free graphs with maximum degree three", J. Graph Theory, 10, pp.477~504 (1986)
- Kuo Chun Lee, "A parallel improvement algorithm for the bipartite subgraph problem", IEEE Transactions on Neural Networks, 3(1), pp.139~145 (1992)
- Rong Long Wang, "A hopfield network learning method for bipartite subgraph problem", IEEE Transactions on Neural Networks, 15(6) (2004)
- Fred Glover, "Future paths for integer programming and links to artificial intelligence", Computers and Operations Research, 13(5), pp.533~549 (1986)
- T.A. Feo, "A probabilistic heuristic for a computationally difficult set covering problem", Operations Research Letters, 8, pp.67~71 (1989)
- P. Festa, "Randomized heuristics for the max-cut problem", Optimization Methods and Software, 7, pp.1033~1058 (2002)
- "DIMACS"[URL]
- "SteinLab"[URL]
- I. Rosseti, "New benchmark instances for the steiner problem in graphs", In Extended Abstracts of the 4th Metaheuristics International Conference, pp.557~561 (2001)
관련 논문AI추천
Tabu Search를 이용한 지름이 2인 그래프에 대한 L(2,1)-coloring 문제 해결김소정, 김찬수, 한근희한국디지털정책학회 · 디지털융복합연구2022 · 제20권 제2호정련법을 이용한 하이퍼그래프 분할김상진, 류명춘, 정영석(사)디지털산업정보학회 · (사)디지털산업정보학회 논문지2013 · 제9권 제4호Simulated Annealing 알고리즘을 이용한 최소 Dominating Set 문제의 효율성 증가에 대한 연구정태의한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2011 · 제18권 제2호선행관계를 가진 다중프로세서 작업들의 Makespan 최소화를 위한 변형타부검색이동주한국산업경영시스템학회 · 한국산업경영시스템학회지2004 · 제27권 제4호타부 리스트가 결합된 유전자 알고리즘을 이용한 트리형 네트워크의 경제적 설계염창선, 이성환, 이한진한국산업경영시스템학회 · 한국산업경영시스템학회지2012 · 제35권 제1호그래프 착색 문제에 적용된 효과적인 Ant Colony Algorithm에 관한 연구안상혁, 이승관, 정태충한국정보처리학회 · 정보처리학회 논문지2004 · 제11권 제2호