지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2013.11
- 수록면
- 159 - 165 (7page)
이용수
초록· 키워드
오류제보하기
본 논문은 NP-완전 문제인 간선 색칠과 그래프 부류 결정 문제를 동시에 해결하는 O(E)의 다항시간 알고리즘을 제안하였다. 제안된 알고리즘은 최대차수-최소차수 정점 쌍 간선을 단순히 선택하는 방법으로 간선 채색수 x'(G)를 결정하였다. 결정된 x'(G)는 △(G)또는 △(G)+1을 얻는다. 결국, 알고리즘 수행 결과 얻은 x'(G)로부터 x'(G) = △(G)이면 부류 1, x'(G) = △(G)+1이면 부류 2로 분류할 수 있다. 또한, 미해결 문제로 알려진 "최대차수가 6인 단순, 평면 그래프는 부류 1이다."라는 Vizing의 평면 그래프 추정도 증명하였다.
목차
등록된 정보가 없습니다.
참고문헌 (14)
참고문헌 신청
이 논문의 저자 정보
최근 본 자료
댓글(0)
0