지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- 한국경영과학회 Management Science and Financial Engineering International Journal of Management Science Vol.13 No.1
- 발행연도
- 2007.5
- 수록면
- 121 - 126 (6page)
이용수
초록· 키워드
오류제보하기
Among many graphs, directed acyclic graph (DAG) attracts many researchers due to its nice property of existence of topological sort. In some classic graph problems, it is known that, if we use the aforementioned property, then much efficient algorithms can be generated. So, in this paper, new algorithm for the all?pairs shortest path problem in a DAG is proposed. While the algorithm performing the iteration, it identifies the set of essential arcs which requires in a shortest path. So, the proposed algorithm has a running time of O(m*n+m), where m, n and m* denote the number of arcs, number of node, and the number of essential arcs in a DAG, respectively.
목차
ABSTRACT
1. Introduction
2. Structural Properties of DAGs
3. Algorithm
4. An Example
References
참고문헌 (6)
참고문헌 신청
1. [학술지(정기간행물)] - Bellman / 1958 / ” Quarterly of Applied Mathematics 16 : 87 ~ 90
2. [학술지(정기간행물)] - Dijkstra / 1959 / “A note on two problems in connexion with graphs : 269 ~ 271
3. [학술지(정기간행물)] - Johnson / 1977 / “Efficient algorithms for shortest paths in sparse networks ” Journal of the ACM 24 : 1 ~ 13
4. [학술지(정기간행물)] - Karger / 1993 / Time bounds for all-pairs shortest paths ” SIAM Journal on Computing 22 : 1199 ~ 1217
5. [학술지(정기간행물)] - Ford / 1962 / Flows in Networks
2. [학술지(정기간행물)] - Dijkstra / 1959 / “A note on two problems in connexion with graphs : 269 ~ 271
3. [학술지(정기간행물)] - Johnson / 1977 / “Efficient algorithms for shortest paths in sparse networks ” Journal of the ACM 24 : 1 ~ 13
4. [학술지(정기간행물)] - Karger / 1993 / Time bounds for all-pairs shortest paths ” SIAM Journal on Computing 22 : 1199 ~ 1217
5. [학술지(정기간행물)] - Ford / 1962 / Flows in Networks
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
Optimization of Sequence Subjects Using Directed Acyclic Graph
한국로고스경영학회 학술발표대회논문집
2005 .07
-
Development of evolutionary algorithm for determining the k most vital arcs in shortest path problem
한국경영과학회 학술대회논문집
2000 .01
-
최단경로문제의 사전처리 해법에 관한 연구
경영과학
2002 .05
-
고등학생들의 생물 그래프 이해 능력 조사
생물교육
2010 .01
-
여자 고등학생들의 생물 그래프 작성 능력 조사
생물교육
2010 .01
-
초등학교 수학과와 사회과의 교과서 분석을 통한 통계 그래프 관련 교육내용 비교 연구
교원교육
2013 .01
-
유방향의 복수 최단 경로 문제 해법 연구
한국경영과학회 학술대회논문집
2008 .05
-
복수 최단 경로의 새로운 해법에 관한 연구
경영과학
2008 .07
-
유방향의 복수 최단 우회 경로 새로운 해법 연구
한국경영과학회 학술대회논문집
2006 .11
-
Classification by feedback structure and partitioning into acyclic subgraphs for a cyclic workflow graph
한국경영과학회 학술대회논문집
2004 .02
-
초등 교사들의 과학교과서 그래프 이해 과정에 대한 안구 운동 분석
초등과학교육
2012 .01
-
중학교 과학 교과서에서 사용된 그래프 유형과 활용 분석
생물교육
2008 .01
-
A Revised Dot Graph : An Alternative to a Bar Performance Graph
의사결정학연구
2014 .12
-
최단경로문제의 다수치명호 해법에 대한 연구 ( Algorithm of the k Most Vital Arcs Problem in Shortest-Path Problem )
한국경영과학회 학술대회논문집
1996 .01
-
초등학생들의 과학 선 그래프 작성 및 해석 과정 분석
초등과학교육
2012 .01
-
그래프이론(DAG)을 이용한 국민소득과 에너지 간의 동시적 인과관계 분석
한국경제연구
2006 .12
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2009-325-016678005