
A Practical Example of GES Application 169
On the basis of (6.6) the graph of moves G
m
=(M, I) can be defined. In
this graph M is the set of moves and I is a E×E matrix where each row is the
vector v
m
l
.InG
m
the i-th node represents the move m
i
with a weight equal
to the number of switched off links, i.e., the |S
m
l
|.InG
m
=(M, I) there is an
undirected edge between nodes i and j if v
m
i
[j] = 1. Then, solving the EAR
problem coincides with finding the maximum clique in G
m
, that is an NP-hard
problem. It is possible to define a greedy algorithm, named Max
Compatibility
Heuristic; the heuristic is able to detect a set of compatible moves, trying to
maximize the num ...