A study on $$k$$ k - $$walk$$ walk generation algorithm to prevent the tottering in graph edit distance heuristic algorithms

SeongCheol Yoon (), Daehee Seo (), Su-Hyun Kim () and Im-Yeong Lee ()
Additional contact information
SeongCheol Yoon: Soonchunhyang University
Daehee Seo: Sangmyung University
Su-Hyun Kim: Soonchunhyang University
Im-Yeong Lee: Soonchunhyang University

Journal of Combinatorial Optimization, 2025, vol. 49, issue 1, No 9, 15 pages

Abstract: Abstract Graph edit distance is usually used for graph similarity checking due to its low information loss and flexibility advantages. However, graph edit distance can’t be used efficiently because it is an NP-Hard problem. Many graph edit distance heuristic algorithms have been proposed to solve this problem. However, some heuristic algorithms for generating $$walk$$ walk generate unnecessary sequences because of the tottering, which leads to many problems. Because of this, various problems arise, like a decrease in approximation accuracy and an increase in execution time. In this paper, we propose an accurate and efficient graph edit distance heuristic algorithm that prevents tottering when generating $$walk$$ walk . When generating $$walk$$ walk , the traversed node‘s information is saved into the queue and then proceeds to traverse the next node. Then, it is possible to prevent the tottering by comparing an existing traversed node with an enqueued one. Through this, we propose a new $$walk$$ walk generation algorithm that prevents generating unnecessary $$walk$$ walk and applies it to existing algorithms to prevent the tottering.

Keywords: Graph; Heuristic algorithm; $$k$$ k - $$walk$$ walk; Tottering (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01236-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:1:d:10.1007_s10878-024-01236-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01236-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().