Article Per Year (5 Year)
p-Index From 2021 - 2026
0.339
P-Index
This Author published in this journals
All Journal TELKOMNIKA (Telecommunication Computing Electronics and Control)
Oleg Sychev
Volgograd State Technical University
Computer Science & IT

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
Methods of finding the maximum common transitive subgraph: experimental comparison Oleg Sychev; Anton Chupinin
TELKOMNIKA (Telecommunication Computing Electronics and Control) Vol 24, No 4: August 2026
Publisher : Universitas Ahmad Dahlan

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.12928/telkomnika.v24i4.27683

Abstract

The problem of finding a maximum common subgraph (MCS) in a graph has broad applications in practical domains. However, certain scenarios require subgraphs with special properties, such as transitivity, that must be kept during building the subgraph. We formally define the concept of a transitive subgraph, investigate its properties. We study four different algorithms for finding the max imum common transitive subgraph (MCTS), compiled a list of tests aim at com paring graphs after making various changes and evaluated their accuracy and efficiency on a set of test cases. Benchmarking on 64 tests ranks the algorithms by scalability and accuracy: branch matching is the most scalable (> 1000 ver tices) and accurate (F1: 0.9907). MCS tree search is viable for graphs of up to ∼ 250 vertices (F1: 0.9752). Backtracking is limited to < 30 vertices (ac curacy: 0.5625), and brute-force is only feasible for graphs with ≤ 10 vertices, despite its high accuracy (0.9375). We discuss the advantages and disadvantages of each method, the test cases where each method demonstrates a non-optimal MCTS,identify the classes on which the methods work correctly and found that the branch matching method based on the longest common subsequence (LCS) algorithm performed the best.
Co-Authors Anton Chupinin