방향과 무 방향 일반 그래프의 최대 사이클 검출 알고리즘 (Algorithm for Maximum Cycle Detection of Directed and Undirected General Graphs)

서지정보

· 발행기관 : 한국인터넷방송통신학회
· 수록지 정보 : 한국인터넷방송통신학회 논문지 / 22권 / 6호 / 91 ~ 97페이지
· 저자명 : 이상운

초록

사이클 검출 문제에 대해, 단일 출발(SS)을 갖는 단일 연결 리스트(SLL)에 한해   복잡도의 거북이와 토끼경주법(HTA)이 제안되었으며, 다중 출발지-다중 종착지, 다중 분기(MSMDMB)를 갖는 일반 그래프에 대해서는 빠른방법이 알려져 있지 않고 있다. 본 논문에서는 MSMDMB를 갖는 주어진 무 방향과 방향 그래프의 최대 사이클을 선형시간 복잡도로 검출할 수 있는 방법을 제안하였다. 제안된 방법은 주어진 원 그래프  에는 사이클 형성 조건을 충족시키지못하는 다수의 정점(또는 노드)가 존재한다는 사실에 기반하여 이들 정점(또는 노드)들을 제거한 축소된 그래프  ′를얻었다. 이 축소된 그래프에 대해 선형시간 복잡도인 선형탐색으로 사이클 집합 와 사이클 길이 를 찾았다. 제안된알고리즘을 실험 데이터에 적용한 결과 모든 데이터들에 대해 최대 사이클을 찾을 수 있음을 보였다.

영어초록

There is hare and tortoise racing algorithm(HTA) for single-source(SS) singly linked list(SLL) with   time complexity. But the fast method is unknown for general graph with multi-source, multi-destination, and multi-branch(MSMDMB). This paper suggests linear time cycle detection algorithm for given undirected and digraph with MSMDMB. The proposed method reduced the given graph  contained with unnecessary vertices(or nodes) to cycle into reduced graph  ′ with only necessary vertices(or nodes) to cycle based on the condition of cycle formation. For the reduced graph  ′, we can be find the cycle set  and cycle length  using linear search within linear time. As a result of experiment data, the proposed algorithm can be obtained the cycle for whole data.

참고자료

· 없음