개인구독
소속 기관이 없으신 경우, 개인 정기구독을 하시면 저렴하게
논문을 무제한 열람 이용할 수 있어요.
지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- Korean Institute of Information Scientists and Engineers 정보과학회 컴퓨팅의 실제 논문지 정보과학회 컴퓨팅의 실제 논문지 제29권 제12호
- 발행연도
- 2023.12
- 수록면
- 577 - 582 (6page)
- DOI
- 10.5626/KTCP.2023.29.12.577
이용수
이 논문의 연구 히스토리 (2)
- 이 논문의 후속연구가 궁금하신가요?
- 연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
- 이 논문의 연구 히스토리 확인하기
초록· 키워드
오류제보하기
최근 제시된 그래프 동형 문제를 빠르게 푸는 알고리즘인 CRaB과 DviCL을 여러 쿼리 그래프에서 실행하여 그 실행 속도를 비교 분석하였다. CRaB은 백트래킹을 통해 그래프 동형을 확인하는 알고리즘이고 DviCL은 분할정복 기법을 사용하여 그래프의 표준형을 찾는 알고리즘이다. CRaB이 DviCL에 비해 비동형인 그래프 쌍을 항상 빠르게 판별하였으며, 동형인 그래프 쌍에 대해서도 대체적으로 더 빠른 실행 속도를 보였다. 또한, 합성 그래프에 대한 실험을 통해 두 알고리즘이 정점 수와 간선 수에 대해 선형에 가까운 실행 시간을 보임을 알 수 있었다. CRaB이 특히 느리게 동작하는 그래프를 특정할 수 있었으며, 이에 대한 추가적인 분석으로 그래프 동형에 대해 더 개선된 알고리즘을 구축할 수 있을 것이라 기대한다.
목차
요약
Abstract
1. 서론
2. 이론적 배경
3. 실험 방법
4. 실험 결과 및 분석
5. 결론
References
참고문헌 (9)
참고문헌 신청
G. Gu, Y. Nam, K. Park, Z. Galil, G. F. Italiano and W.-S. Han, “Scalable Graph Isomorphism: Combining Pairwise Color Refinement and Backtracking via Compressed Candidate Space,” in ICDE, pp. 1368-1379, 2021.
B. D. McKay, “Practical graph isomorphism,” Congressus Numerantium, vol. 30, pp. 45-87, 1981.
B. D. McKay and A. Piperno, “Practical graph isomorphism, II,” Journal of Symbolic Computation, vol. 60, pp. 94-112, 2014.
C. Lu, J. X. Yu, Z. Zhang and H. Cheng, “Graph Iso/Auto-morphism: A Divide-&-Conquer Approach,” in SIGMOD, pp. 1195-1207, 2021.
G. Gu, Y. Nam, K. Park, Z. Galil, G. F. Italiano and W.-S. Han, “Efficient Graph Isomorphism Query Processing using Degree Sequences and Color-Label Distributions,” in ICDE, pp. 872-884, 2022.
B. D. McKay, “Practical graph isomorphism,” Congressus Numerantium, vol. 30, pp. 45-87, 1981.
B. D. McKay and A. Piperno, “Practical graph isomorphism, II,” Journal of Symbolic Computation, vol. 60, pp. 94-112, 2014.
C. Lu, J. X. Yu, Z. Zhang and H. Cheng, “Graph Iso/Auto-morphism: A Divide-&-Conquer Approach,” in SIGMOD, pp. 1195-1207, 2021.
G. Gu, Y. Nam, K. Park, Z. Galil, G. F. Italiano and W.-S. Han, “Efficient Graph Isomorphism Query Processing using Degree Sequences and Color-Label Distributions,” in ICDE, pp. 872-884, 2022.
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
그래프 동형 문제를 위한 최신 알고리즘 비교
한국정보과학회 학술발표논문집
2023 .06
-
Improving Subgraph Isomorphism with Pruning by Bipartite Matching
Journal of KIISE
2021 .09
-
요약 그래프 상에서 효과적인 그래프 압축 기법
한국정보과학회 학술발표논문집
2016 .06
-
퇴각 검색 기반의 그래프 동형 알고리즘
한국정보과학회 학술발표논문집
2015 .06
-
동적 그래프에서 효율적인 그래프 요약 기법
한국정보과학회 학술발표논문집
2015 .12
-
부분 그래프 동형 문제를 위한 동적 매칭 순서들의 성능 비교
정보과학회 컴퓨팅의 실제 논문지
2020 .01
-
그래프 중심성들을 이용한 그래프 유사도 측정
한국컴퓨터정보학회논문지
2018 .12
-
외부 지식 그래프 결합을 위한 그래프 트랜스포머 알고리즘
한국정보과학회 학술발표논문집
2023 .06
-
An Embedding Technique for Weighted Graphs using LSTM Autoencoders
Journal of KIISE
2021 .01
-
확장 그래프에서 그래프 신경망을 사용한 다 기준 추천
한국통신학회 학술대회논문집
2023 .02
-
그래프의 정점 연결성에 대한 최소 범위 할당
한국정보통신학회논문지
2017 .11
-
그래프 오더링을 활용한 그래프 병렬 처리의 성능 향상
한국정보과학회 학술발표논문집
2017 .12
-
GPU를 이용한 경로 기반 하이브리드 그래프 처리 기법
정보과학회 컴퓨팅의 실제 논문지
2024 .11
-
최신 그래프 처리 시스템에서의 동적 그래프를 위한 업데이트 수행 방식에 대한 조사
한국정보과학회 학술발표논문집
2018 .06
-
이질형 그래프에서의 간선 예측을 위한 고차 그래프 뉴럴 네트워크
한국정보과학회 학술발표논문집
2021 .06
-
GPU에서 CUDA를 이용한 그래프 유사도 측정을 위한 병렬 알고리즘
정보과학회 컴퓨팅의 실제 논문지
2017 .03
-
그래프 데이터베이스 성능평가를 위한 랜덤 그래프 생성과 질의
한국정보과학회 학술발표논문집
2016 .12
-
그래프 구조 학습 적용을 통한 그래프 신경망의 분자 특성 예측 성능 향상
한국정보과학회 학술발표논문집
2024 .06
-
디스크 기반 그래프 엔진의 입출력 성능 향상을 위한 그래프 오더링
정보과학회 컴퓨팅의 실제 논문지
2018 .01
-
소셜 그래프 생성을 위한 스케일러블 그래프 확산 모델
한국통신학회 학술대회논문집
2025 .02
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-151-24-02-089226982