서지주요정보
네트워크 단절문제에 대한 수리 모형과 휴리스틱 해법 = Mathematical models and a heuristic algorithm for the graph disconnection problem
서명 / 저자 네트워크 단절문제에 대한 수리 모형과 휴리스틱 해법 = Mathematical models and a heuristic algorithm for the graph disconnection problem / 오상민.
저자명 오상민 ; Oh, Sang-Min
발행사항 [대전 : 한국과학기술원, 2003].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8013961

소장위치/청구기호

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

MIE 03019

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

초록정보

This thesis considers a Graph Disconnection Problem(GDP), which is to find a set of edges and nodes such that the total cost of removing the edges is no more than a given budget while maximizing the total weight of nodes disconnected from a given source node. We propose two new models, which have polynomial number of constraints and variables compared to the previous model that has exponential number of constraints. Since this problem is NP-hard, we propose a meta-heuristic algorithm. This algorithm consists of two stages; preprocessing stage and tabu search stage. The preprocessing stage reduces the problem size. We examined infeasible solutions as well as feasible solutions in the tabu search. We tested the algorithm on 360 instances which were randomly generated and obtained optimal solutions except for 20 instances.

서지기타정보

서지기타정보
청구기호 {MIE 03019
형태사항 ii, 46 p. : 삽도 ; 26 cm
언어 한국어
일반주기 저자명의 영문표기 : Sang-Min Oh
지도교수의 한글표기 : 박성수
지도교수의 영문표기 : Sung-Soo Park
학위논문 학위논문(석사) - 한국과학기술원 : 산업공학과,
서지주기 참고문헌 : p. 45-46
주제 네트워크 단절 문제
타부 탐색
수리모형
graph disconnection problem
tabu search
mathematical model
QR CODE qr code