지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술대회자료
- 저자정보
- 발행연도
- 2024.10
- 수록면
- 207 - 210 (4page)
이용수
초록· 키워드
오류제보하기
본 연구는 주어진 그래프가 ‘채색 그래프’인지 판단하고, ‘채색 그래프’라면 그래프의 부분 그래프 중 가장 큰 완전그래프인 ‘Max Clique’의 개수 및 차수, 그리고 이를 이루는 정점들의 집합을 모두 찾는 효율적인 알고리즘에 대해 다룬다. ‘채색 그래프’란 주어진 그래프의 ‘Max Clique’의 차수가 K일 때 K가 2 이하이거나 간선으로 연결된 두 점을 다른 색으로 칠할 때 K가지 색으로만 모든 정점을 칠할 수 있는 그래프이다. 주어진 그래프의 점 개수를 N, 간선 개수를 E, ‘Max Clique’의 차수 및 개수를 각각 K, G라 하면 그래프의 Max Clique 점 집합을 모두 구하는 Naive한 알고리즘(Bron-Kerbosch Algorithm)은 최적화를 거쳐도 O(GN) 이상의 시간복잡도가 걸린다. 이는 점 개수와 최대 클리크의 개수가 많은 그래프에서 매우 비효율적이다. 본 연구는 연결된 두 정점을 같은 색으로 칠하지 않도록 하고, 각 점마다 해당 점이 가질 수 없는 색과 그 제약을 주는 다른 정점을 모두 저장하는 방식으로 문제를 해결한다. 차수가 K+1인 완전그래프에서 간선 하나를 뺀 그래프가 없으면 항상 채색 그래프임이 증명되었으며, 이 알고리즘은 시간복잡도 O(ElogN+GK), 공간복잡도 O(N²)이하를 만족하며 정확하게 동작함을 테스트 데이터에 대하여 증명할 수 있다. 본 알고리즘은 유전자 클러스트에서 강한 상호작용을 효율적으로 찾아내어 특정 유전자를 찾아내는 등의 분야에 응용될 수 있을 것으로 기대한다.
목차
요약
ABSTRACT
Ⅰ. 서론
Ⅱ. 연구 과정
Ⅲ. 실제 구현
Ⅳ. 결론
References
참고문헌 (0)
참고문헌 신청함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
최대 클릭 문제의 분할정복 알고리즘
한국정보기술학회논문지
2015 .06
-
그래프 중심성들을 이용한 그래프 유사도 측정
한국컴퓨터정보학회논문지
2018 .12
-
싸이클 수 증가를 통한 Extended Least Difference Greedy Clique-cover 알고리즘의 개선
한국통신학회 학술대회논문집
2018 .06
-
그래프의 정점 연결성에 대한 최소 범위 할당
한국정보통신학회논문지
2017 .11
-
인덱스 부호 최적화를 위한 Extended Least Difference Greedy Clique-cover 알고리즘의 개선
한국통신학회 학술대회논문집
2018 .01
-
중심성이 높은 정점의 변화에 따른 네트워크 특성 분석
한국컴퓨터정보학회논문지
2017 .03
-
Erdos-Faber-Lovasz 추측 증명 알고리즘
한국인터넷방송통신학회 논문지
2015 .01
-
The Classification of random graph models using graph centralities
한국컴퓨터정보학회논문지
2019 .07
-
그래프 정보를 이용한 그래프 구조 간략화 알고리즘
제어로봇시스템학회 국내학술대회 논문집
2016 .03
-
A Graph Embedding Technique for Weighted Graphs Based on LSTM Autoencoders
JIPS(Journal of Information Processing Systems)
2020 .01
-
그래프데이터베이스 기반 통신망 운영관리 방안
한국정보통신학회 종합학술대회 논문집
2022 .05
-
동적 그래프에서 효율적인 그래프 요약 기법
한국정보과학회 학술발표논문집
2015 .12
-
Max-Plus Control Design for Regulating Token Delay in the Closed-Loop System
대한산업공학회 춘계공동학술대회 논문집
2015 .04
-
요약 그래프 상에서 효과적인 그래프 압축 기법
한국정보과학회 학술발표논문집
2016 .06
-
특허 지식그래프를 위한 지식 그래프 임베딩 모델 분석 연구
Proceedings of KIIT Conference
2020 .10
-
An Embedding Technique for Weighted Graphs using LSTM Autoencoders
Journal of KIISE
2021 .01
-
외부 지식 그래프 결합을 위한 그래프 트랜스포머 알고리즘
한국정보과학회 학술발표논문집
2023 .06
-
그래프 채색 알고리즘의 GPGPU 상 구현 및 최적화
정보과학회 컴퓨팅의 실제 논문지
2022 .12
-
Unified Graph Clustering via Learning Robust and Structured Graph
대한전자공학회 학술대회
2019 .06
-
최신 그래프 처리 시스템에서의 동적 그래프를 위한 업데이트 수행 방식에 대한 조사
한국정보과학회 학술발표논문집
2018 .06
최근 본 자료
댓글(0)
0