TELK
OMNIKA
T
elecommunication,
Computing,
Electr
onics
and
Contr
ol
V
ol.
24,
No.
4,
August
2026,
pp.
1187
∼
1196
ISSN:
1693-6930,
DOI:
10.12928/TELK
OMNIKA.v24i4.27683
❒
1187
Methods
of
nding
the
maximum
common
transiti
v
e
subgraph:
experimental
comparison
Oleg
Syche
v,
Anton
Chupinin
Department
of
Softw
are
for
Automated
Systems,
F
aculty
of
Electronics
and
Computer
Engineering,
V
olgograd
State
T
echnical
Uni
v
ersity
,
V
olgograd,
Russia
Article
Inf
o
Article
history:
Recei
v
ed
No
v
20,
2025
Re
vised
Mar
19,
2026
Accepted
Mar
29,
2026
K
eyw
ords:
Backtracking
Branch
matching
Directed
ac
yclic
graph
Dynamic
programming
Heuristic
method
Maximum
common
transiti
v
e
graph
ABSTRA
CT
The
problem
of
nding
a
maximum
common
subgraph
(MCS)
in
a
graph
has
broad
applications
in
practical
domains.
Ho
we
v
er
,
certain
sce
narios
require
subgraphs
with
special
properties,
such
as
transiti
vity
,
that
must
be
k
ept
during
b
uilding
the
subgraph.
W
e
formally
dene
the
concept
of
a
transiti
v
e
subgraph,
in
v
estig
ate
its
properties.
W
e
study
four
dif
ferent
algorithms
for
nding
the
max-
imum
common
transiti
v
e
subgraph
(MCTS),
compiled
a
list
of
tests
aim
at
com-
paring
graphs
after
making
v
arious
changes
and
e
v
aluated
their
accurac
y
and
ef
cienc
y
on
a
set
of
test
cases.
Benchmarking
on
64
tests
ranks
the
algorithms
by
scalability
and
accurac
y:
branch
matching
is
the
most
scalable
(
>
1000
v
er
-
tices)
and
accurate
(F1:
0.9907).
MC
S
tree
search
is
viable
for
graphs
of
up
to
∼
250
v
ertices
(F1:
0.9752).
Backtracking
is
limited
to
<
30
v
ertices
(ac-
curac
y:
0.5625),
and
brute-force
is
only
feasible
for
graphs
with
≤
10
v
ertices,
despite
its
high
accurac
y
(0.9375).
W
e
discuss
the
adv
antages
and
disadv
antages
of
each
method,
the
test
cases
where
each
method
demonstrates
a
non-optimal
MCTS,
identify
the
classes
on
which
the
methods
w
ork
correctly
and
found
that
the
branch
matching
method
based
on
the
longest
common
subsequence
(LCS)
algorithm
performed
the
best.
This
is
an
open
access
article
under
the
CC
BY
-SA
license
.
Corresponding
A
uthor:
Ole
g
Syche
v
Department
of
Softw
are
for
Automated
Systems,
F
aculty
of
Electronics
and
Computer
Engineering
V
olgograd
State
T
echnical
Uni
v
ersity
28
Lenina
Prospect,
400005
V
olgograd,
Russia
Email:
oasyche
v@gmail.com
1.
INTR
ODUCTION
The
problem
of
nding
a
maximum
common
subgraph
(MCS)
has
a
wide
range
of
applications.
The
MCS
algorithm
ca
n
be
a
po
werful
tool
in
molecular
analysis
[1]-[3],
chemistry
[4],
[5],
reconguration
plan-
ning
of
modular
robotic
s
ystems
[6],
structural
health
monitoring
[7]
tracking
[8]
and
general
graph
similarity
learning
[9]-[11].
The
problem
of
nding
the
MCS
is
nondeterministic
polynomial-time
hard
(NP-hard)
in
the
gener
al
case.
Ho
we
v
er
,
there
are
se
v
eral
approximation
methods
that
can
nd
not
necessarily
optimal
b
ut
close
to
optimal
solutions
[12].
In
addition,
there
are
special
classes
of
graphs
for
which
the
problem
of
nding
the
MCS
can
be
solv
ed
in
polynomial
time
[13].
F
or
e
xample,
for
graphs
with
unique
node
labels,
the
MCS
can
be
found
unambiguously
using
the
intersections
of
the
v
erte
x
and
edge
sets.
F
or
trees,
an
algorithm
based
on
dynamic
programming
is
used,
which
relies
on
bipartite
matching
of
the
v
ertices
of
the
tw
o
trees
compared
[14].
J
ournal
homepage:
http://telk
omnika.uad.ac.id
Evaluation Warning : The document was created with Spire.PDF for Python.
1188
❒
ISSN:
1693-6930
There
is
also
an
approach
using
quadrati
c
unconstrained
binary
optimization
(Q
UBO)
objecti
v
e
functions
for
nding
the
MCS
.
P
arallel
[15]
and
genetic
[16]
approaches
ha
v
e
also
been
used
for
nding
MCS.
Additionally
,
machine
learning
(ML)
is
often
used
in
the
MCS
search
problem
[17]-[20].
There
are
also
approaches
and
attempts
to
inte
grate
lar
ge
language
models
(LLMs)
into
graph-related
tasks
[21].
There
also
e
xist
specialized
MCS
with
additional
properties
[22].
One
of
the
less-st
ud
i
ed
cases
of
the
MCS
problem
is
the
common
subgraph
that
preserv
es
transiti
v
e
dependencies
between
nodes
when
deleting
nodes
that
do
not
t
the
conditions
of
the
common
subgraph.
Preserving
transiti
v
e
dependencies
in
a
directed
ac
yclic
graph
(D
A
G)
allo
ws
one
to
retain
relationships
l
ik
e
“X
precedes
Y”
e
v
en
when
an
intermediate
node
cannot
be
included
in
the
common
subgraph.
One
of
practical
cases
of
preserving
transiti
vity
when
b
uilding
the
MCS
is
the
comparison
of
softw
are
repositories.
Repositories
that
use
branchi
ng
can
be
understood
as
D
A
G
storing
the
transiti
v
e
relationships
of
precedence
between
re
visions.
The
pre
vious
studies
ha
v
e
demonstrated
ef
cienc
y
of
using
the
longest
common
subsequences
(LCS)
algorithm
in
teaching
programming
and
foreign
languages
[23],
[24].
Git
is
an
i
mportant
tool
in
modern
softw
are
de
v
elopment,
and
l
earning
ho
w
to
use
v
ersion
control
tool
is
a
crucial
step
in
training
highly
skilled
information
technology
(IT)
specialists
.
Numerous
studies
sho
w
that
using
specialized
automatic
tutors
in
student
education
can
signicantly
accelerate
the
learning
process
[25],
[26].
But
implementing
an
ef
fecti
v
e
tutor
requires
the
ability
to
nd
the
maximum
common
transiti
v
e
subgraph
(MCTS)
to
identify
misplaced,
missing,
and
e
xtraneous
nodes
(change
sets)
in
the
student’
s
answer
[27].
In
this
w
ork,
we
propose
a
v
ariant
of
the
MCS
problem
that
accounts
for
transiti
v
e
relationships
in
D
A
Gs.
W
e
dene
the
MCTS,
compare
se
v
eral
methods
for
nding
it,
and
analyze
the
comparison
results.
The
paper
is
structured
as
follo
ws.
Section
2
pro
vides
the
k
e
y
denitions
necessary
to
understand
the
subject.
Section
3
describes
the
prospecti
v
e
methods
of
nding
the
MCTS:
brute-force
search
of
all
possible
v
ariants,
an
adaptation
of
dynamic
programming
method
for
nding
the
m
aximum
common
subtree,
a
heuristic
method
based
on
matching
each
branch
of
graph
G
1
with
the
closest
branch
of
graph
G
2
and
calculating
their
LCS
and
backtracking
method
for
unique
node
label.
Section
4
outlines
the
core
test
cases
and
pro
vides
a
rationale
for
the
selected
test
cases.
Section
5
presents
the
e
xperimental
results,
and
section
6
contains
the
study
conclusions.
2.
KEY
DEFINITIONS
In
this
section,
the
basic
concepts
and
terminology
used
throughout
the
paper
are
introduced.
Denition
1.
A
gr
aph
is
denoted
as
G
=
(
V
,
E
)
,
wher
e
V
is
the
set
of
vertices
(nodes)
and
E
⊆
V
×
V
is
the
set
of
edg
es
(connections
between
vertices).
Denition
2.
A
D
A
G
is
a
dir
ected
gr
aph
that
does
not
contain
dir
ected
cycles.
In
other
w
ords,
starting
from
a
v
erte
x
v
and
follo
wing
the
direction
of
the
arcs,
it
is
impossible
to
return
to
the
original
v
erte
x
v
.
Denition
3.
Let
G
=
(
V
,
E
)
be
a
dir
ected
gr
aph.
The
complete
tr
ansitive
r
emo
val
of
the
verte
x
v
is
t
he
oper
ation
that
for
all
distinct
vertices
u
1
,
.
.
.
,
u
n
∈
V
and
w
1
,
.
.
.
,
w
m
∈
V
satisfying:
∀
i,
j
:
(
u
i
,
v
)
∈
E
∧
(
v
,
w
j
)
∈
E
(1)
pr
oduces
a
gr
aph
G
′
=
(
V
′
,
E
′
)
wher
e:
V
′
=
V
\
{
v
}
,
E
′
=
(
E
\
{
(
u
i
,
v
)
,
(
v
,
w
j
)
|
∀
i,
j
}
)
∪
{
(
u
i
,
w
j
)
|
∀
i,
j
}
(2)
That
is,
when
a
v
erte
x
v
is
remo
v
ed,
for
each
of
its
ancestors,
an
edge
is
created
connecting
it
to
each
of
v
erte
x
v
’
s
descendants.
Denition
4.
A
gr
aph
G
1
=
(
V
1
,
E
1
)
is
called
a
tr
ansitive
subgr
aph
of
G
=
(
V
,
E
)
if
ther
e
e
xists
a
gr
aph
G
′
1
isomorphic
to
G
1
that
can
be
obtained
fr
om
G
by
applying
a
nite
number
(possibly
zer
o)
of
tr
ansiti
ve
r
emo
vals
of
the
verte
x.
Denition
5.
A
gr
aph
G
∗
is
called
the
MCTS
of
gr
aphs
G
1
and
G
2
if:
(1)
G
∗
is
a
tr
ansitive
subgr
aph
of
both
G
1
and
G
2
;
(2)
Ther
e
e
xists
no
other
common
tr
ansitive
subgr
aph
G
′
of
G
1
and
G
2
with
|
V
(
G
′
)
|
>
|
V
(
G
∗
)
|
.
TELK
OMNIKA
T
elecommun
Comput
El
Control,
V
ol.
24,
No.
4,
August
2026:
1187–1196
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
T
elecommun
Comput
El
Control
❒
1189
Figure
1
sho
ws
the
MCTS
of
the
tw
o
graphs.
Figure
1.
MCTS
3.
METHOD
3.1.
Brute-f
or
ce
sear
ch
The
brute-force
method
for
nding
the
MCTS
is
based
on
analyzing
all
possible
mappings
between
the
v
ertices
of
tw
o
graphs
G
1
=
(
V
1
,
E
1
)
and
G
2
=
(
V
2
,
E
2
)
.
Assuming
|
V
1
|
≤
|
V
2
|
,
the
algorithm
e
xamines
all
possible
biject
ions
between
subsets
V
′
1
⊆
V
1
and
V
′
2
⊆
V
2
,
where
|
V
′
2
|
=
|
V
′
1
|
.
At
the
same
time,
the
graph
structure
is
preserv
ed:
if
v
1
,
u
1
∈
V
1
and
v
2
,
u
2
∈
V
2
,
then
under
the
biject
ion
mapping
v
1
to
v
2
and
u
1
to
u
2
,
the
v
erte
x
relations
must
be
maintained:
if
u
1
is
a
descendant
of
v
1
,
then
u
2
must
be
a
descendant
of
v
2
.
The
goal
is
to
select
the
mapping
with
the
maximum
number
of
correct
v
erte
x
bijections.
First,
the
method
selects
the
k
v
ertices
of
G
1
and
matches
them
to
k
v
ertices
of
G
2
.
T
o
search
and
v
erify
the
number
of
v
alid
bijecti
v
e
v
erte
x
mappings
for
a
complete
graph
matching,
it
is
necessary
to
tra
v
erse
all
v
ertices
of
both
graphs
using
depth-rst
search
(DFS)
or
breadth-rst
search
(BFS)
and
to
store
all
transiti
v
e
connections
for
each
graph
before
comparing
them.
Note
that,
for
labeled
graphs,
the
number
of
possible
mappings
can
be
reduced
by
requiring
label
equality
for
the
corresponding
v
ertices,
which
can
signicantly
speed
up
the
solution
in
practical
applications.
The
brute-force
method
guarantees
an
e
xact
solution
for
nding
the
MCTS,
as
it
e
xhausti
v
ely
enu-
merates
all
possible
subgraphs
and
selects
the
optimal
one,
b
ut
due
to
the
comple
xity
of
O
(
n
!
·
2
n
)
,
where
n
is
the
number
of
v
ertices
in
the
lar
gest
graph,
its
use
is
limited
to
small
graphs.
The
k
e
y
adv
antage
of
e
xhausti
v
e
search
is
its
absolute
accurac
y
,
though
its
e
xponential
comple
xity
limits
practical
applications.
F
or
labeled
graphs,
optimization
is
possible
through
v
erte
x-label
matching,
which
reduces
the
search
space.
Despite
its
computational
limitations,
this
method
remains
the
gold
standard
for
v
erifying
approximation
algorithms.
3.2.
Adapting
the
maximum
common
subtr
ee
sear
ch
method
using
dynamic
pr
ogramming
to
solv
e
the
pr
oblem
of
computing
the
maximum
common
transiti
v
e
subtr
ee.
F
or
solving
problems
related
to
nding
the
maximum
common
subtree
of
tw
o
trees
[14],
there
e
xists
a
specic
algorithm
that
emplo
ys
dynamic
programming
and
a
maximum-weight
matching
algorithm.
Adapting
this
method
to
nd
the
MCTS
could
allo
w
solving
a
wide
range
of
problems
with
a
lo
wer
time
comple
xity
that
brute-force
search,
allo
wing
the
analysis
of
lar
ger
graphs.
The
algorithm
uses
an
approach
that
determines
the
v
alue
of
a
parent
v
erte
x
through
the
v
alues
of
its
child
v
ertices.
Three
main
cases
need
to
be
considered:
matching
v
ertices,
matching
one
v
erte
x
with
the
descendants
of
the
other
,
and
matching
the
second
v
erte
x
with
the
descendants
of
the
rst.
If
a
v
erte
x
u
from
graph
G
1
can
be
matched
with
a
v
erte
x
v
from
graph
G
2
,
then
a
set
of
pairs
of
v
erte
x
matching
from
graph
Methods
of
nding
the
maximum
common
tr
ansitive
subgr
aph:
e
xperimental
comparison
(Ole
g
Syc
he
v)
Evaluation Warning : The document was created with Spire.PDF for Python.
1190
❒
ISSN:
1693-6930
G
1
to
graph
G
2
should
be
created
for
these
v
ertices,
and
the
pair
(
u,
v
)
should
be
added.
Ne
xt,
it
is
necessary
to
iterate
through
all
descendants
of
u
and
v
and
construct
a
weight
matrix
for
each
pair
of
descendants
of
the
v
ertices
u
and
v
.
Then,
using
an
algorithm
to
nd
the
ma
x
i
mum
weight
matching,
we
determine
the
best
pairs
among
the
descendants.
F
or
the
cases
of
comparing
v
ertices
with
descendants,
it
is
necessary
to
select
a
pair
where
the
weight
of
the
pair
is
maximal.
Then,
for
the
current
pair
of
v
ertices,
it
is
necessary
to
choose
the
best
result
among
the
three
presented.
The
complete
algorithm
is
sho
wn
in
Algorithm
1.
Algorithm
1
Maximum
common
transiti
v
e
subtree
pr
ocedur
e
M
A
X
T
R
A
N
S
I
T
S
U
B
T
R
E
E
(
u,
v
,
G
1
,
G
2
,
dp
)
l
ef
t
←
∅
▷
Case
1:
match
u
and
v
center
←
∅
▷
Case
2:
skip
v
,
recurse
on
children
of
u
r
ig
ht
←
∅
▷
Case
3:
skip
u
,
recurse
on
children
of
v
if
u
=
v
then
▷
Only
match
if
labels
agree
l
ef
t
←
l
ef
t
∪
{
(
u,
v
)
}
Initialize
matrix
M
f
or
all
u
′
∈
C
hil
dr
en
(
G
1
,
u
)
do
f
or
all
v
′
∈
C
hil
dr
en
(
G
2
,
v
)
do
subg
r
aph
←
M
A
X
T
R
A
N
S
I
T
S
U
B
T
R
E
E
(
u
′
,
v
′
,
G
1
,
G
2
,
dp
)
Add
subg
r
aph
to
M
[
u
′
,
v
′
]
end
f
or
end
f
or
match
←
M
A
X
W
E
I
G
H
T
M
A
T
C
H
I
N
G
(
M
,
dp
)
▷
Find
best
child
pairing
l
ef
t
←
l
ef
t
∪
{
match
}
end
if
f
or
all
u
′
∈
C
hil
dr
en
(
G
1
,
u
)
do
center
←
max(
center
,
M
A
X
T
R
A
N
S
I
T
S
U
B
T
R
E
E
(
u
′
,
v
,
G
1
,
G
2
,
dp
))
end
f
or
f
or
all
v
′
∈
C
hil
dr
en
(
G
2
,
v
)
do
r
ig
ht
←
max(
r
i
g
ht,
M
A
X
T
R
A
N
S
I
T
S
U
B
T
R
E
E
(
u,
v
′
,
G
1
,
G
2
,
dp
))
end
f
or
dp
[
u,
v
]
←
max(
l
ef
t,
center
,
r
ig
ht
)
▷
Choose
lar
gest
set
r
etur
n
dp
[
u,
v
]
end
pr
ocedur
e
Since
the
Hung
arian
algorithm
(with
time
comple
xity
O
(
n
3
)
)
is
used
to
nd
the
maximum
weight
matching,
the
total
time
comple
xity
of
the
algorithm
is
O
(
n
5
)
,
where
n
is
the
number
of
v
ertices
in
the
graph.
3.3.
Heuristic
method
based
on
matching
branches
of
tw
o
graphs
This
heuristic
method
is
based
on
the
idea
that
dif
ferent
branches
in
a
Git
repository
ha
v
e
a
di
v
erse
set
of
changes.
Each
change
can
be
vie
wed
as
a
label
on
the
v
ertices
(commits).
It
follo
ws
that,
when
tw
o
graphs
ha
v
e
similar
characteristics
to
a
Git
repository
,
it
is
necessary
to
match
each
branch
of
graph
G
1
to
the
branch
of
graph
G
2
that
is
most
similar
,
such
that
each
branch
of
G
1
is
matched
with
only
one
branch
from
G
2
,
and
each
branch
of
G
2
is
matched
with
only
one
branch
from
G
1
.
Subsequently
,
for
each
such
pair
,
it
is
necessary
to
nd
the
LCS
of
v
ertices,
considering
that
some
v
ertices
may
contain
multiple
labels,
and
there
may
be
cases
of
incomplete
label
correspondence
for
v
ertices
that
we
include
in
the
LCS.
T
o
this
end,
it
will
be
necess
ary
to
us
e
a
modie
d
v
ersion
of
the
LCS
algorithm
s
uch
that,
in
addi
tion
to
maximizing
the
length
of
the
subsequence,
it
minimizes
the
number
of
mismatched
labels.
L
[
i,
j
]
=
0
,
if
i
=
0
or
j
=
0
,
max(
L
[
i
−
1
,
j
]
,
L
[
i,
j
−
1]
,
L
[
i
−
1
,
j
−
1]
+
v
[
i
][
j
])
,
if
x
i
can
compare
y
j
,
max(
L
[
i
−
1
,
j
]
,
L
[
i,
j
−
1])
,
otherwise.
(3)
Let
B
(
G
)
denote
the
list
of
all
branches
in
graph
G
.
Then,
the
number
of
matched
branch
pairs
between
graphs
G
1
and
G
2
is
equal
to
min
{|
B
(
G
1
)
|
,
|
B
(
G
2
)
|}
.
The
time
comple
xity
of
the
LCS
algorithm
is
O
(
n
·
m
)
,
where
n
and
m
are
the
lengths
of
the
sequences;
in
our
case,
this
is
the
number
of
v
ertices
in
the
branch.
Considering
all
of
this,
the
o
v
erall
comple
xity
of
the
heuristic
method
is
O
(min
{|
B
(
G
1
)
|
,
|
B
(
G
2
)
|}
·
n
·
m
)
,
which
is
signicantly
lo
wer
than
the
time
comple
xities
of
the
algorithms
that
were
described
abo
v
e.
TELK
OMNIKA
T
elecommun
Comput
El
Control,
V
ol.
24,
No.
4,
August
2026:
1187–1196
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
T
elecommun
Comput
El
Control
❒
1191
Some
v
ertices
may
belong
to
se
v
eral
branches
at
once,
causing
a
single
v
erte
x
to
participate
multi
ple
times
in
the
LCS
search
operations
(
comple
xity
O
(
n
2
)
),
which
implies
that
the
algorithm’
s
comple
xity
is
O
(
n
2
·
k
)
,
where
n
is
the
number
of
v
ertices
and
k
is
the
number
of
branches.
3.4.
Backtracking
method
tr
ee
f
or
unique
node
label
It
is
w
orth
noting
that
primarily
for
educational
purposes,
to
teach
students
ho
w
to
w
ork
with
v
ersion
control
system
(VCS),
repositories
are
used
where
dif
fs
in
commits
are
unique.
These
repositories
can
be
vie
wed
as
trees
with
unique
node
labels,
where
each
v
erte
x
is
assigned
e
xactly
one
label,
i
mplying
that
for
e
v
ery
v
erte
x
v
∈
G
1
,
there
is
a
unique
corresponding
v
erte
x
u
∈
G
2
.
F
or
each
v
erte
x
of
each
tree,
we
compute
the
list
of
all
its
ancestors.
Then,
we
perform
a
DFS
algorithm
of
the
rst
tree
G
1
,
proceeding
from
the
root
to
the
lea
v
es.
During
this
tra
v
ersal,
for
each
v
erte
x
we
e
xamine
the
list
of
its
ancestors
in
the
second
tree
G
2
and
the
corresponding
branches
in
G
1
.There
is
no
need
to
consider
branches
all
of
whos
e
v
ertices
belong
to
another
branch;
formally
,
we
disre
g
ard
an
y
branch
B
such
that
∃
B
′
̸
=
B
with
V
(
B
)
⊆
V
(
B
′
)
.
T
w
o
branches
are
conicting
if
the
y
contain
a
pair
of
conicting
v
ertices.
V
ertices
u
and
v
are
conict-
ing
if
u
is
not
an
ancestor
of
v
in
G
1
,
whil
e
u
′
is
an
ancestor
of
v
′
in
G
2
.
F
ormally
,
(
u,
v
)
are
conicting
⇐
⇒
u
̸⪯
G
1
v
∧
u
′
⪯
G
2
v
′
where
⪯
G
denotes
the
ancestor
relation
in
tree
G
.
During
the
backtracking
phas
e
once
we
ha
v
e
obta
ined
the
list
of
acti
v
e
branches
containing
v
for
each
v
erte
x
v
,
we
handle
the
case
where
v
has
tw
o
or
more
direct
children.
If
deg
+
(
v
)
≥
2
,
(i.e.,
v
has
direct
children
u
1
,
u
2
,
.
.
.
,
u
n
with
n
≥
2
),
we
must
select
a
set
of
no
n-
conicting
branches
–
each
containing
one
of
the
children
u
1
,
u
2
,
.
.
.
,
u
n
–
and
attempt
to
mer
ge
them
into
a
single
branch,
which
is
added
to
the
global
branch
list.
F
or
this
algorithm,
the
solution
is
the
lar
gest
branch
by
cardinality
.
The
time
comple
xity
of
the
backtracking
method
is
O
(
n
!)
,
where
n
is
the
number
of
branches
in
the
graph.
4.
TEST
SAMPLE
When
creating
the
tests
necessary
to
v
erify
the
correctness
of
the
methods
for
nding
the
m
aximum
transiti
v
e
subgraph,
we
based
on
the
properties
of
possible
practical
usage:
comparing
tw
o
Git
repositories
of
the
same
project
when
learning
to
use
Git.
The
number
of
v
ertices
for
the
majority
of
test
graphs
is
7-12
v
ertices
(up
to
20
v
ertices),
which
is
suf
cient
for
testing
basic
graph
transformation
cases.
W
e
considered
dif
ferent
types
of
changes
in
the
graph
(which
are
interpreted
as
errors).
One
class
of
errors
dif
ferent
placement
of
v
erte
x
labels
(i.e.,
a
label
being
remo
v
ed
from
a
v
erte
x,
an
e
xtra
label
being
added
to
a
v
erte
x,
or
the
label
mo
v
ed
to
another
v
erte
x).
The
latter
case
can
be
interpreted
as
a
combination
of
tw
o
operations:
de
leting
the
label
from
one
v
erte
x
and
adding
it
to
another
.
F
or
the
errors
of
this
type,
a
linear
graph
(also
called
a
bamboo)
is
suf
cient.
The
other
kind
of
dif
ferences
is
the
dif
ferences
in
the
order
of
v
ertices.
Examples
include
deleting
an
leaf
v
erte
x,
deleting
a
v
erte
x
from
the
middle
of
the
graph
(which
has
descendant
v
ertices),
adding
a
v
erte
x
to
the
middle,
adding
a
v
erte
x
to
the
end
and
changing
the
v
erte
x
placement.
There
are
also
more
specic
changes,
such
as
mer
ging
se
v
eral
v
ertices
into
one
(remo
ving
a
v
ert
e
x
and
adding
all
its
labels
to
another
v
erte
x)
and
splitting
a
single
v
erte
x
i
nto
a
fe
w
v
ertices.
F
or
those
changes,
directed
trees
with
2–3
branches
are
used.
This
is
important
for
testing
the
methods’
ability
to
correctly
identify
changes
in
the
branching
structure.
It
is
also
important
to
v
erify
if
the
method
correctly
handles
the
mer
ging
of
multiple
branches
into
one
and
accurately
processes
other
changes
when
the
branches
are
mer
ged.
W
e
also
made
comple
x
tests
for
combinations
of
the
graph
changes
described
abo
v
e.
T
able
1
sho
ws
the
main
parameters
that
were
combined
to
create
dif
ferent
tests
and
their
v
alues;
T
able
2
sho
ws
a
part
of
the
test
sample
using
the
short
names
of
parameters.
T
able
1.
T
est
parameters
T
est
parameter
Short
name
V
alues
Graph
type
type
D
A
G,
directed
tree
Number
of
v
ertices
v
ertices
1,
3-8,
12-15,
16-20
Number
of
branches
br
anches
1,
2-3
Number
of
v
erte
x
labels
labels
0,
1,
2
or
more
Number
of
changes
dif
f
0,
1,
2
or
more
Methods
of
nding
the
maximum
common
tr
ansitive
subgr
aph:
e
xperimental
comparison
(Ole
g
Syc
he
v)
Evaluation Warning : The document was created with Spire.PDF for Python.
1192
❒
ISSN:
1693-6930
T
able
2.
T
est
cases
No.
Name
G
1
type
G
1
v
ertices
G
1
labels
G
1
branches
G
2
type
G
2
v
ertices
G
2
labels
G
2
branches
dif
f.
1
Equal
trees
T
ree
10
1-2
1
T
ree
10
1-2
1
0
2
Equal
D
A
Gs
D
A
G
14
1
3
D
A
G
14
1
3
0
3
V
erte
x
deleted
in
middle
T
ree
7
1
3
T
ree
6
3
1
1
4
Leaf
deleted
T
ree
7
1
3
T
ree
6
3
1
1
...
20
Branch
deleted
T
ree
9
1
3
T
ree
7
2
1
2
21
Re
v
ersed
branch
T
ree
6
1
1
T
ree
6
1
6
5
22
D
A
G
branch
deleted
D
A
G
11
1
3
T
ree
9
2
1
2
...
35
Label
added
T
ree
10
1
2-3
T
ree
10
1
1
1
36
Label
missing
T
ree
10
1
2-3
T
ree
10
1
1
1
...
50
One
v
erte
x
split
into
se
v
eral
T
ree
6
1-4
1
T
ree
7
1-2
1
2
...
63
Comple
x
test
5
T
ree
8
2-3
2
T
ree
8
2-3
2
4
64
Comple
x
test
6
T
ree
8
1-2
2
T
ree
10
2-3
2
4
This
test
suite
co
v
ers
most
of
the
error
cases
that
arise
when
students
w
ork
independently
to
master
v
ersion
control
systems
and
learn
repository-editing
skills
using
the
pro
vided
tools.
5.
RESUL
TS
This
section
presents
the
results
of
testing
the
listed
algorithms
on
the
listed
set
of
tests
that
s
imulate
the
results
of
performing
tasks
for
students
to
w
ork
with
control
systems.
A
comparison
of
the
methods
with
the
performance
of
the
DeepSeek-V3.2
model
is
also
carried
out,
for
which
a
prompt
w
as
specically
engi-
neered
to
nd
MCTS.
Metrics
such
as
precision,
recall,
and
F1
will
be
used
to
e
v
aluate
the
accura
c
y
of
MCTS
determination.
F
or
the
condence
interv
al
of
the
pass
rate
metric,
the
W
ilson
score
interv
al
with
a
95%
con-
dence
le
v
el
is
used.
F
or
this
purpose,
the
follo
wing
v
ertices
are
dened:
true
positi
v
e
(TP)
–
a
pair
of
v
ertices
matched
by
the
algorithm
that
is
present
in
the
reference
set.
F
alse
positi
v
e
(FP)
–
a
pair
of
v
ertices
predicted
by
the
algorithm
b
ut
absent
in
the
reference
set.
F
als
e
ne
g
ati
v
e
(FN)
–
a
pair
of
v
ertices
from
the
reference
set
not
found
by
the
algorithm.
T
rue
ne
g
ati
v
e
(TN)
–
an
y
other
pair
of
v
ertices
(not
predicted
by
the
algorithm
and
not
included
in
the
reference
set).
All
tests
were
conducted
on
a
computer
with
an
Apple
M2
processor
and
16
GB
of
random
access
memory
(RAM).
The
DeepSeek
model
successfully
passed
37
tests
(pass
rate
0.58).
Ho
we
v
er
,
it
frequently
made
errors
when
matching
graph
nodes,
indicating
certain
dif
culties
in
correctly
interpreting
the
structure
of
graph
data
or
their
interconnections.
The
brute-force
method
demonstrated
a
hi
gh
pass
rate
(0.94).
All
f
ailed
tests
had
e
xcessi
v
ely
long
e
x
ecution
times,
which
necessitated
the
termination
of
these
tests.
Ho
we
v
er
,
it
scales
poorly
with
the
graph
size.
F
or
instance,
on
a
graph
with
just
11
v
ertices,
this
method
can
tak
e
about
2
minutes
to
nd
an
answer
,
while
other
methods
solv
e
it
in
under
one
second.
Furthermore,
there
is
a
si
gnicant
issue
with
memory
consumption.
F
or
a
graph
of
12
v
ertices,
the
method
already
requires
more
than
5
GB
of
RAM.
The
backtracking
method
for
tree-based
unique
node
labeling
sho
wed
the
lo
west
pass
rate
among
all
algorithms
tested
(0.56).
The
primary
set
of
tests
where
this
algorithm
incorrectl
y
identies
the
maximum
transiti
v
e
subgraph
in
v
olv
ed
graphs
with
v
ertices
containing
multiple
labels
and
graphs
with
repeated
labels.
Additionally
,
all
tests
in
which
the
graphs
were
D
A
Gs
indicate
that
this
algorithm
is
unsuitable
for
checking
repositories
with
multiple
branch
mer
ges.
The
method
demonstrates
acceptable
runtime
performance
for
graphs
with
a
number
of
v
ertices
n
<
30
.
Ho
we
v
er
,
as
n
increases
be
yond
this
threshold
and
the
graph’
s
branching
f
actor
gro
ws,
the
e
x
ecution
time
scales
accordingly
.
The
ne
xt
algorithm
in
terms
of
pass
rate
(0.83)
is
the
method
adapting
dynamic
programming
for
nding
the
maximum
transiti
v
e
subtree.
The
primary
class
of
problems
where
this
method
made
errors
in
v
olv
es
comparing
graphs
after
remo
ving
a
common
parent
of
multiple
branches.
In
this
case,
the
correct
solution
w
ould
be
to
match
corr
esponding
v
ertices
in
the
compared
graphs,
b
ut
the
method
instead
proposes
discarding
smaller
branches
and
retaining
only
the
lar
gest
branch
in
the
matching.
Performance
testi
ng
re
v
ealed
that
the
TELK
OMNIKA
T
elecommun
Comput
El
Control,
V
ol.
24,
No.
4,
August
2026:
1187–1196
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
T
elecommun
Comput
El
Control
❒
1193
proposed
method
maintains
f
ast
e
x
ecution
on
graphs
with
the
number
of
v
ertices
n
>
100
,
which
is
comparable
to
the
scale
of
real-w
orld
repositories.
The
heuristic
method
based
on
matching
each
branch
of
the
graph
performed
best
on
this
test
set,
achie
ving
a
pass
rate
of
0.98.
It
successfully
handled
tas
k
s
in
v
olving
graphs
without
branch
mer
ges,
reposito-
ries
with
mer
ges,
graphs
with
repeated
label
s,
and
graphs
with
unique
label
sets.
It
demonstrated
high
speed
in
e
x
ecuting
test
cases.
The
method
only
performed
poorly
in
a
test
where
tw
o
or
more
branches
of
a
graph
had
identical
label
sets
b
ut
dif
fered
in
the
order
of
v
ert
e
x
arrangement,
leading
to
incorrect
matching
of
cor
-
responding
branches
across
dif
ferent
graphs
and
f
ailure
to
identify
the
MCTS.
This
method
pro
v
ed
to
be
the
most
performance,
maintaining
f
ast
e
x
ecution
on
graphs
with
n
>
1000
v
ertices.
All
methods
are
in
one
w
ay
or
another
suited
for
a
specic
class
of
graphs
on
which
the
y
correctly
locate
the
MCTS.
When
the
MCTS
search
is
incorrect,
the
methods
return
not
the
maximum,
b
ut
one
of
the
common
transiti
v
e
subgraphs.
It
is
possible
to
use
se
v
eral
methods
at
once
to
search
for
the
MCTS
and
choose
the
lar
gest
output
.
The
T
able
3
presents
a
comprehensi
v
e
comparison
of
these
algorithms.
T
able
4
and
Figure
2
demonstrate
the
program’
s
e
x
ecution
time
as
a
function
of
the
number
of
v
ertices
in
the
graph.
Figure
3(a)
presents
an
e
xample
of
tw
o
graphs
on
which
the
backtracking
method
performs
an
incorrect
search;
Figure
3(b)
sho
ws
an
e
xample
of
tw
o
graphs
where
the
adapted
dynamic
programming
method
conducts
an
incorrect
search;
Figure
3(c)
illustrates
an
e
xample
of
tw
o
graphs
where
the
heuristic
matching-based
method
f
ails
to
perform
a
correct
search.
T
able
3.
T
est
results
No
Method
P
assed
F
ailed
P
ass
rate
C
I
95%
Precision
Recall
F1-score
1
Bruteforce
60
4
0.9375
0.8500–0.9754
1.0000
0.8843
0.9386
2
MCS
tree
search
53
11
0.8281
0.7178–0.9012
0.9952
0.9560
0.9752
3
Branch
matching
63
1
0.9844
0.9167–0.9972
0.9953
0.9861
0.9907
4
Backtracking
36
28
0.5625
0.4409–0.6771
0.9922
0.8796
0.9325
5
deepseek-v3.2
37
27
0.5781
0.4561–0.6913
0.8986
0.8819
0.8902
T
able
4.
Algorithm
performance
by
problem
size
(seconds)
Number
of
v
ertices
Method
9
10
11
25
30
32
34
50
100
200
250
1000
5000
Branch
0.20
0.20
0.20
0.22
0.23
0.22
0.22
0.23
0.22
0.26
0.29
0.64
8.00
MCS
tree
search
0.03
0.03
0.03
0.07
0.10
0.11
0.10
0.35
6.00
120.0
360.0
–
–
Backtracking
0.03
0.03
0.03
0.64
8.00
24.00
105.0
–
–
–
–
–
–
Bruteforce
2.00
20.00
99.00
–
–
–
–
–
–
–
–
–
–
Figure
2.
Performance
comparison
of
four
algorithms
Methods
of
nding
the
maximum
common
tr
ansitive
subgr
aph:
e
xperimental
comparison
(Ole
g
Syc
he
v)
Evaluation Warning : The document was created with Spire.PDF for Python.
1194
❒
ISSN:
1693-6930
(a)
(b)
(c)
Figure
3.
Graphs
for
which
the
methods
f
ail:
(a)
backtracking,
(b)
MCS
tree
search,
and
(c)
branch
matching
6.
CONCLUSION
Finding
MCTS
is
necessary
for
nding
changes
in
transiti
v
e
D
A
Gs,
which
can
be
used,
to
v
erify
students’
w
orks
when
learning
to
use
v
ersion
control
systems
lik
e
Git.
W
e
considered
four
methods
of
nd-
ing
MCTS
and
designed
a
test
sample
to
study
their
ef
cienc
y
when
dif
ferent
changes
to
graphs
were
made.
Experimental
results
conrmed
the
theoretical
e
xpectation
that
the
w
orst-performing
methods
w
ould
be
the
LLM-based
method
(0.58)
and
the
backtracking
method
(0.56).
The
brute-force
method
achie
v
ed
perfect
ac-
curac
y
,
b
u
t
only
on
small
graphs
(
n
<
10)
.
The
best
o
v
erall
performance
w
as
demonstrated
b
y
the
branch
matching
method
(0.98),
which
f
ailed
only
on
graphs
containing
highly
simi
lar
branches.
The
MCS
tree
search
method
yielded
a
solid
result
(0.83),
although
it
underperformed
relati
v
e
to
initial
e
xpectations.
Although
none
of
the
methods
solv
ed
all
test
cases,
we
identied
distinct
graph
classes
where
each
method
tends
to
f
ail.
That
enables
dynamic
selection
or
combination
of
methods
based
on
graph
structure
–
for
e
xample,
by
multiple
xing
approaches
or
running
se
v
eral
in
parallel
and
select
ing
the
best
result
using
a
“bag
of
e
xperts”
strate
gy
–
to
fur
-
ther
impro
v
e
o
v
erall
accurac
y
.
The
studied
methods
will
be
used
in
de
v
eloping
an
intelligent
tutoring
system
for
teaching
v
ersion
control,
which
is
important
for
training
programmers
and
IT
specialists.
Finding
MCTS
between
the
correct
solution
reposi
tory
and
the
student’
s
repository
will
allo
w
detection
of
missing,
e
xtraneous,
misplaced
and
wrong
commits,
which
can
be
sho
w
to
the
student
with
appropriate
messages.
That
will
allo
w
training
with
feedback
without
human
in
the
loop,
which
signicantly
increases
the
number
of
solv
ed
tasks
and
the
resulting
skills
compared
to
manual
v
erication.
FUNDING
INFORMA
TION
The
study
w
as
carried
out
wi
th
the
support
of
the
Center
for
Digital
Scientic
and
Educational
Projects
and
De
v
elopments
in
the
Field
of
Industrial
Articial
Intelligence
(C2RED-AI)
of
V
olgograd
State
T
echnical
Uni
v
ersity
,
created
as
part
of
the
implementation
of
top-le
v
el
educational
programs
in
the
eld
of
articial
intelligence
(Agreement
No.
70-2025-000756).
A
UTHOR
CONTRIB
UTIONS
ST
A
TEMENT
This
journal
uses
the
C
o
nt
rib
utor
Roles
T
axonomy
(CRediT)
to
recognize
indi
vidual
author
contrib
u-
tions,
reduce
authorship
disputes,
and
f
acilitate
collaboration.
TELK
OMNIKA
T
elecommun
Comput
El
Control,
V
ol.
24,
No.
4,
August
2026:
1187–1196
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
T
elecommun
Comput
El
Control
❒
1195
Name
of
A
uthor
C
M
So
V
a
F
o
I
R
D
O
E
V
i
Su
P
Fu
Ole
g
Syche
v
✓
✓
✓
✓
✓
✓
✓
✓
✓
Anton
Chupinin
✓
✓
✓
✓
✓
✓
✓
✓
C
:
C
onceptualization
I
:
I
n
v
estig
ation
V
i
:
V
i
sualization
M
:
M
ethodology
R
:
R
esources
Su
:
Su
pervision
So
:
So
ftw
are
D
:
D
ata
Curation
P
:
P
roject
Administration
V
a
:
V
a
lidation
O
:
Writing
-
O
riginal
Draft
Fu
:
Fu
nding
Acquisition
F
o
:
F
o
rmal
Analysis
E
:
Writing
-
Re
vie
w
&
E
diting
CONFLICT
OF
INTEREST
ST
A
TEMENT
Authors
state
no
conict
of
interest.
D
A
T
A
A
V
AILABILITY
The
data
supporting
the
ndings
of
this
study
are
openly
a
v
ailable
in
the
GitHub
Project
Repository
at
https://github
.com/v
akhe
w1900/master
-dis/tree/main
REFERENCES
[1]
M.
Stroet
et
al.
,
“OfraMP:
a
fragment-based
tool
to
f
acilitate
the
parametrization
of
lar
ge
molecules,
”
J
ournal
of
Computer
-Aided
Molecular
Design
,
v
ol.
37,
no.
8,
pp.
357–371,
2023,
doi:
10.1007/s10822-023-00511-7.
[2]
L.
Schietg
at
et
al.
,
“
Automated
detection
of
toxicophores
and
prediction
of
mutagenicity
using
PMCSFG
algorithm,
”
Molecular
Informatics
,
v
ol.
42,
no.
3,
p.
2200232,
2023,
doi:
10.1002/minf.202200232.
[3]
N.
P
arisutham,
“Ho
w
do
centrality
measures
help
to
predict
similarity
patterns
in
molecular
chemical
structural
graphs?”
Articial
Intellig
ence
Chemistry
,
v
ol.
1,
no.
2,
p.
100007,
2023,
doi:
10.1016/j.aichem.2023.100007.
[4]
T
.-L.
Phan
et
al.
,
“Reaction
rebalancing:
a
no
v
el
approach
to
curating
reaction
databases,
”
J
ournal
of
Cheminf
ormatics
,
v
ol.
16,
no.
1,
p.
82,
2024,
doi:
10.1186/s13321-024-00875-4.
[5]
Y
.
Chang
et
al.
,
“High-entrop
y
allo
y
electrocatalysts
screened
using
machine
learning
informed
by
quantum-inspired
similarity
analysis,
”
Matter
,
v
ol.
7,
no.
11,
pp.
4099–4113,
2024,
doi:
10.1016/j.matt.2024.10.001.
[6]
C.
Zhang,
L.
Zhou,
and
Y
.
Li,
“P
areto
optimal
reconguration
planning
and
distrib
uted
parallel
motion
control
of
mobile
modular
robots,
”
IEEE
T
r
ansactions
on
Industrial
Electr
onics
,
v
ol.
71,
no.
8,
pp.
9255–9264,
2024,
doi:
10.1109/TIE.2023.3321997.
[7]
J.
Goslig
a,
D.
Hester
,
K.
W
orden,
and
A.
Bunce,
“On
population-based
structural
health
monitoring
for
bridges,
”
Mec
hanical
Systems
and
Signal
Pr
ocessing
,
v
ol.
173,
p.
108919,
2022,
doi:
10.1016/j.ymssp.2022.108919.
[8]
U.
Ahmed,
G.
Sri
v
asta
v
a,
Y
.
Djenouri,
and
J.
C.-W
.
Lin,
“Kno
wledge
graph
based
trajectory
outlier
detection
in
sustainable
smart
cities,
”
Sustainable
Cities
and
Society
,
v
ol.
78,
p.
103580,
2022,
doi:
10.1016/j.scs.2021.103580.
[9]
Z.
Lan,
B.
Hong,
Y
.
Ma,
and
F
.
Ma,
“More
interpretable
graph
similarity
computation
via
maximum
common
subgraph
inference,
”
IEEE
T
r
ansactions
on
Knowledg
e
and
Data
Engineering
,
v
ol.
36,
no.
11,
pp.
6588–6599,
2024,
doi:
10.1109/TKDE.2024.3387044.
[10]
Z.
Liu,
Y
.
Chen,
N.
Liu,
J.
He,
and
D.
Li,
“Graph2re
gion:
Ef
cient
graph
similarity
learning
with
structure
and
scale
restoration,
”
IEEE
T
r
ansactions
on
Knowledg
e
and
Data
Engineering
,
v
ol.
37,
no.
12,
pp.
7213–7225,
2025,
doi:
10.1109/TKDE.2025.3617461.
[11]
C
.
Zou,
G.
Lu,
L.
Du,
X.
Zeng,
and
S.
Lin,
“Graph
similarity
learning
for
cross-le
v
el
interactions,
”
Information
Pr
ocessing
&
Mana
g
ement
,
v
ol.
62,
no.
1,
p.
103932,
2025,
doi:
10.1016/j.ipm.2024.103932.
[12]
L.
Cardone
and
S.
Quer
,
“The
multi-maxi
mum
and
quasi-maxi
mum
common
subgra
ph
problem,
”
Computation
,
v
ol.
11,
no.
4,
p.
69,
2023,
doi:
10.3390/computation11040069.
[13]
D.
J.
Aldous,
“On
the
lar
gest
common
subtree
of
random
leaf-labeled
binary
trees,
”
SIAM
J
ournal
on
Discr
ete
Mathematics
,
v
ol.
36,
no.
1,
pp.
299–314,
2022,
doi:
10.1137/20M1347504.
[14]
A.
Gupta
and
N.
Nishimura,
“Finding
lar
gest
subtrees
and
smallest
supertrees,
”
Algorithmica
,
v
ol.
21,
no.
2,
pp.
183–210,
1998,
doi:
10.1007/PL00009212.
[15]
V
.
V
asilchik
o
v
,
“Recursi
v
e-parallel
algorithm
for
solving
the
maximum
common
subgraph
problem,
”
A
utomatic
Contr
ol
and
Com-
puter
Sciences
,
v
ol.
58,
no.
7,
pp.
827–835,
2024,
doi:
10.3103/S0146411624700287.
[16]
C.
V
alenti,
“
A
genetic
approach
to
the
maximum
common
subgraph
problem,
”
in
Pr
oceedings
of
the
20th
International
Confer
ence
on
Computer
Systems
and
tec
hnolo
gies
,
2019,
pp.
98–104,
doi:
10.1145/3345252.3345272.
[17]
S.
Quer
,
T
.
Madeo,
A.
Calabrese,
G.
Squillero,
and
E.
Carraro,
“Node
embedding
and
cosine
similarity
for
ef
cient
maximum
common
subgraph
disco
v
ery
,
”
Applied
Sciences
,
v
ol.
15,
no.
16,
p.
8920,
2025,
doi:
10.3390/app15168920.
[18]
I.
Ro
y
,
S.
Chakrabarti,
and
A.
De,
“Maximum
common
subgraph
guided
graph
retrie
v
al:
late
and
early
interaction
netw
orks,
”
Advances
in
Neur
al
Information
Pr
ocessing
Systems
,
v
ol.
35,
pp.
32
112–32
126,
2022.
[19]
K.
S.
Y
o
w
,
N.
Liao,
S.
Luo,
and
R.
Cheng,
“Machine
learning
for
subgraph
e
xtraction:
Methods,
applications
and
challenges,
”
Pr
oceedings
of
the
VLDB
Endowment
,
v
ol.
16,
no.
12,
pp.
3864–3867,
2023,
doi:
10.14778/3611540.3611571.
[20]
Z.
Y
an,
C.
Ding,
L.
Ma,
L.
Cao,
and
H.
Y
ou,
“Rotated
graph
similarity
computation
via
graph
transformer
netw
orks,
”
Neur
ocom-
puting
,
v
ol.
658,
p.
131474,
2025,
doi:
10.1016/j.neucom.2025.131474.
[21]
X.
Ren,
J.
T
ang,
D.
Y
in,
N.
Cha
wla,
and
C.
Huang,
“
A
surv
e
y
of
lar
ge
language
models
for
graphs,
”
in
Pr
oceedings
of
the
30th
A
CM
SIGKDD
Confer
ence
on
Knowledg
e
Disco
very
and
Data
Mining
,
2024,
pp.
6616–6626,
doi:
10.1145/3637528.3671460.
Methods
of
nding
the
maximum
common
tr
ansitive
subgr
aph:
e
xperimental
comparison
(Ole
g
Syc
he
v)
Evaluation Warning : The document was created with Spire.PDF for Python.
1196
❒
ISSN:
1693-6930
[22]
E.
de
Gastines
and
A.
Knippel,
“F
ormulations
for
the
maximum
common
edge
subgraph
problem,
”
Discr
ete
Applied
Mathematics
,
v
ol.
346,
pp.
115–130,
2024,
doi:
10.1016/j.dam.2023.11.044.
[23]
O.
Syche
v
,
“Questions
for
teaching
phrase
b
uilding
with
automatic
feedback,
”
Softwar
e
Impact
s
,
v
ol.
15,
p.
100461,
Mar
.
2023,
doi:
10.1016/j.simpa.2022.100461.
[24]
E.
No
v
ozhenina,
O.
Syche
v
,
O.
T
opork
o
v
a,
and
O.
Evtushenk
o,
“T
eaching
english
w
ord
order
with
correctwriting
softw
are,
”
in
Computational
Science
and
Its
Applications
–
ICCSA
2021
.
Springer
International
Publishing,
2021,
p.
681–692,
doi:
10.1007/978-
3-030-86970-0
47.
[25]
A.
W
.
F
.
K
ouam,
“The
ef
fecti
v
eness
of
intelligent
tutoring
systems
in
supporting
st
udents
with
v
arying
le
v
els
of
programming
e
xperience,
”
Disco
ver
Education
,
v
ol.
3,
no.
1,
p.
278,
2024,
doi:
10.1007/s44217-024-00385-3.
[26]
A.
Lieb
and
T
.
Goel,
“Student
interaction
with
Ne
wtBot:
An
LLM-as-tutor
Chatbot
for
Secondary
Ph
ysics
Education,
”
in
Extended
Abstr
acts
of
the
CHI
Confer
ence
on
Human
F
actor
s
in
Computing
Systems
,
ser
.
CHI
EA
’24.
Ne
w
Y
ork,
NY
,
USA:
Association
for
Computing
Machinery
,
2024,
doi:
10.1145/3613905.3647957.
[27]
O.
Syche
v
and
D.
Mamonto
v
,
“
Automatic
error
detection
and
hint
generation
in
the
teaching
of
formal
languages
syntax
using
correctwriting
question
type
for
moodle
lms,
”
in
2018
3r
d
Russian-P
acic
Confer
ence
on
Computer
T
ec
hnolo
gy
and
Applications
(RPC)
,
2018,
pp.
1–4,
doi:
10.1109/RPC.2018.8482125.
BIOGRAPHIES
OF
A
UTHORS
Oleg
Syche
v
recei
v
ed
the
M.Sc.
de
gree
in
Computer
Science
and
Engineering
from
V
olgograd
State
T
echnical
Uni
v
ersity
,
R
ussia.
He
is
a
Associate
Professor
of
Softw
are
Engineer
-
ing
Department,
V
olgograd
State
T
echnical
Uni
v
ersity
,
V
olgograd,
Russia.
He
is
currently
w
orking
on
the
design
and
implementation
of
intelligent
tutoring
systems
capable
of
presenting
w
ork
ed
e
x-
amples,
determining
semantic
errors,
and
pro
viding
e
xplanatory
feedback
on
wh
y
an
answer
is
in-
correct—specically
detai
ling
what
subject-domain
rules
are
brok
en.His
research
i
nterests
in
v
olv
es
de
v
eloping
systems
to
ask
follo
w-up
questions
to
stimulate
student
thinking
and
automatically
clas-
sify
generated
questions
to
minimize
direct
human
in
v
olv
ement
in
the
creation
of
assessments,
all
based
on
a
single
subject-domain
model.
His
professional
e
xperience
spans
23
years,
including
22
years
in
scientic
and
pedagogical
w
ork.
He
can
be
contacted
at
email:
oasyche
v@gmail.com.
Anton
Chupinin
recei
v
ed
the
B.Eng.
de
gree
in
Softw
are
Engineering
from
V
olgograd
State
T
echnical
Uni
v
ersity
(VSTU),
V
olgograd,
Russia,
in
2024.
He
is
currently
a
graduate
student
of
the
M.Eng.
de
gree
in
the
same
eld.
He
is
also
a
back
end
de
v
eloper
in
the
V
olg
ablob
compan
y
.
His
research
interests
in
v
olv
es
de
v
eloping
intelligent
tut
oring
systems
for
teaching
computer
science.
He
can
be
contacted
at
email:
antchupinin@gmail.com.
TELK
OMNIKA
T
elecommun
Comput
El
Control,
V
ol.
24,
No.
4,
August
2026:
1187–1196
Evaluation Warning : The document was created with Spire.PDF for Python.