지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2015.5
- 수록면
- 31 - 39 (9page)
이용수
초록· 키워드
오류제보하기
방향 가중 그래프의 차수제약 최소신장트리 (degree-constrained minimum spanning tree, d-MST) 문제는 정확한 해를 구하는 다항시간 알고리즘이 존재하지 않아 NP-완전 문제로 알려져 왔다. 따라서 휴리스틱한 근사 알고리즘을 적용하여 최적 해를 구하고 있다. 본 논문은 차수와 사이클을 검증하는 Kruskal 알고리즘으로 d-MST의 초기 해를 구하고, d-MST의 초기 해에 대해 k-opt를 수행하여 최적 해를 구하는 다항시간 알고리즘을 제안하였다. 제안된 알고리즘을 4개의 그래프에 적용한 결과 2-MST까지 최적 해를 구할 수 있었다.
목차
요약
Abstract
Ⅰ. 서론
Ⅱ. 관련 연구와 연구배경
Ⅲ. k-opt d-MST 알고리즘
Ⅳ. 실험 및 결과 분석
Ⅴ. 결론
REFERENCES
참고문헌 (18)
참고문헌 신청
1. [학술지(정기간행물)] - O. Borůvka / 1926 / OJistemProblemuMinimalnim / Prace Mor. Prrodved. Spol. V Brne (Acta Societ. Natur. Moravicae) 3 (3) : 37 ~ 58
2. [학술지(정기간행물)] - J. Nešetřil / 2001 / Otakar Borůvka on Minimum Spanning Tree Problem (Translation of the both 1926 Papers, Comments, History) / DMATH: DiscreteMathematics 233 (1)
3. [학술지(정기간행물)] - R. C. Prim / 1957 / Shortest ConnectionNetworks and Some Generalisations / Bell SystemTechnical Journal 36 (6) : 1389 ~ 1401
4. [학술대회논문] - J. B. Kruskal / 1956 / On the Shortest Spanning Subtree and The Traveling Salesman Problem / Proceedings of the AmericanMathematical Society 7 : 48 ~ 50
5. [인터넷자원] - Wikipedia / / Minimum Spanning Tree
2. [학술지(정기간행물)] - J. Nešetřil / 2001 / Otakar Borůvka on Minimum Spanning Tree Problem (Translation of the both 1926 Papers, Comments, History) / DMATH: DiscreteMathematics 233 (1)
3. [학술지(정기간행물)] - R. C. Prim / 1957 / Shortest ConnectionNetworks and Some Generalisations / Bell SystemTechnical Journal 36 (6) : 1389 ~ 1401
4. [학술대회논문] - J. B. Kruskal / 1956 / On the Shortest Spanning Subtree and The Traveling Salesman Problem / Proceedings of the AmericanMathematical Society 7 : 48 ~ 50
5. [인터넷자원] - Wikipedia / / Minimum Spanning Tree
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
단순한 차수 제약 최소신장트리 알고리즘
한국정보기술학회논문지
2015 .10
-
Comparison of Workload Perception for Original and Modified Cognitive Tasks
Industrial Engineering & Management Systems
2019 .12
-
최대 클릭 문제의 분할정복 알고리즘
한국정보기술학회논문지
2015 .06
-
The Mst1/2-BNIP3 axis is required for mitophagy induction and neuronal viability under mitochondrial stress
Experimental and Molecular Medicine
2024 .03
-
Nodes-Constrained Minimum Spanning Tree Problems
대한산업공학회 춘계공동학술대회 논문집
2018 .04
-
DNN과 k-opt를 적용한 대규모 외판원 문제의 최적 해법
한국인터넷방송통신학회 논문지
2015 .01
-
PS-InSAR 기법의 긴밀도 향상을 위한 최적의 MST 기법 연구
한국측량학회 학술대회자료집
2019 .04
-
Opt Tree: Write Optimized Tree Using Optane DCPM Internal Buffer
Journal of KIISE
2021 .07
-
최소 되먹임 간선 집합 문제 알고리즘
한국컴퓨터정보학회논문지
2015 .03
-
셀 형성 문제의 기계배치순서 결정 알고리즘
한국컴퓨터정보학회논문지
2016 .04
-
차량과 드론을 혼용한 최적 라우팅을 위한 휴리스틱
한국컴퓨터정보학회논문지
2016 .09
-
UVLM 및 MST를 적용한 복합관절 조류모방 비행체 날갯짓 공력 분석
항공우주시스템공학회 학술행사 논문집
2024 .10
-
제약표현과 최소자승법을 이용한 쿼드로터의 근사 최적궤적 생성
한국항공우주학회 학술발표회 초록집
2022 .04
-
이변수 다항식 문제에 대한 새로운 메타 휴리스틱 개발
산업경영시스템학회지
2021 .01
-
신장트리 오토마타를 활용한 유사 화합물 탐색 알고리즘
한국정보과학회 학술발표논문집
2022 .12
-
단측-최적화 배정과 교환 알고리즘을 적용한 할당문제의 양측-최적화
한국컴퓨터정보학회논문지
2015 .12
-
개척자 기반 새로운 최적화 알고리즘: POA (Pioneer-inspired Optimization Algorithm)
한국지능시스템학회 논문지
2021 .12
-
Polynomial Time Algorithm for Satellite Communications Scheduling Problem with Capacity Constrainted Transponder
한국컴퓨터정보학회논문지
2016 .06
-
무기 목표물 배정 문제의 최대 치사인원 선택 알고리즘
한국인터넷방송통신학회 논문지
2019 .01
-
Efficient and Robust Implementation of the Algorithms for Parity-Constrained k-Center and Facility Location
Journal of KIISE
2021 .03
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2016-325-001889462