Reputation: 442
I have two graphs G1
and G2
, possibly with colored nodes and edges. Does there exist a function (either MatLab or some other program) that answers the following question:
G1
, say f(G1)
, such that f(G1)
is greater than or equal to (element-wise dominance)G2
?I am aware of the function isisomorphic
introduced in R2016B
. This checks answers the question: Given two graphs G1
and G2
, possibly with colored nodes and edges, are G1
and G2
isomorphic? One method would be to enumerate all isomorphisms of G1
and check the above condition. For larger graphs this seems like it would take too long.
Edit: An answer to this question might be to modify the isomorphism
function in MatLab
-- we could replace conditions of the form f(G1) == G2
with f(G1) >= G2
. The isomorphism
function in the @graph toolbox
first re-orders the graphs for efficient computation later, then it calls the isomorphism
function in the @biograph toolbox
. This consequently calls the graphisomorphism
function, which then calls the Mex
files graphalgs
, which appears to be a version of the nauty Trace package
, see here. So, in short, it would seem that to answer this question I would need to modify the nauty package
.
Upvotes: 1
Views: 339