부분 그래프 매칭 문제를 위한 새로운 동적 매칭 순서와 성능 비교 


49권  1호, pp. 1-7, 1월  2022
10.5626/JOK.2022.49.1.1


PDF

  요약

최근 다양한 분야에서 그래프 분석이 사용되고 있다. 그래프 분석에서 가장 핵심적인 문제 중 하나는 부분 그래프 매칭(subgraph matching) 문제이다. 부분 그래프 매칭 문제는 데이터 그래프와 쿼리그래프가 주어졌을 때 데이터 그래프에서 쿼리 그래프의 모든 임베딩(embedding)을 찾는 문제이다. 그동안 이 문제를 해결하는 백트래킹 기반의 많은 알고리즘이 연구되어왔다. 본 논문에서는 이 문제를 해결하는 최신 알고리즘인 DAF에서 제안한 동적 매칭 순서의 문제점을 분석하고 이를 개선한 동적 매칭 순서를 소개한다. 또한, 제안한 매칭 순서를 실제 데이터 그래프를 가지고 실험을 진행하여 가지치기 기법을 사용하지 않았거나 가지치기 기법을 사용하더라도 수행 시간이 매우 짧지 않으면 이전 매칭 순서들보다 효과적임을 입증하였다.


  통계
2022년 11월부터 누적 집계
동일한 세션일 때 여러 번 접속해도 한 번만 카운트됩니다. 그래프 위에 마우스를 올리면 자세한 수치를 확인하실 수 있습니다.
  논문 참조

[IEEE Style]

S. Min, W. Shin, C. Kim, K. Park, "New Adaptive Matching Order and Performance Comparison for Subgraph Matching Problem," Journal of KIISE, JOK, vol. 49, no. 1, pp. 1-7, 2022. DOI: 10.5626/JOK.2022.49.1.1.


[ACM Style]

Seunghwan Min, Wonseok Shin, Chaewon Kim, and Kunsoo Park. 2022. New Adaptive Matching Order and Performance Comparison for Subgraph Matching Problem. Journal of KIISE, JOK, 49, 1, (2022), 1-7. DOI: 10.5626/JOK.2022.49.1.1.


[KCI Style]

민승환, 신원석, 김채원, 박근수, "부분 그래프 매칭 문제를 위한 새로운 동적 매칭 순서와 성능 비교," 한국정보과학회 논문지, 제49권, 제1호, 1~7쪽, 2022. DOI: 10.5626/JOK.2022.49.1.1.


[Endnote/Zotero/Mendeley (RIS)]  Download


[BibTeX]  Download



Search




Journal of KIISE

  • ISSN : 2383-630X(Print)
  • ISSN : 2383-6296(Electronic)
  • KCI Accredited Journal

사무국

  • Tel. +82-2-588-9240
  • Fax. +82-2-521-1352
  • E-mail. chwoo@kiise.or.kr