4
$\begingroup$

If the two graphs are isomorphic, then their distance is zero. And this distance increases, if vertices or edges are added or removed to/from one of the graphs.

Does this "distance" have a special name, or definition?

This distance function should return the minimal number of steps, to transform one graph to an another given graph, using edge/vertex adding/removing

The graph may be directed or not, but the edges aren't weighted (in my case)


Note: I don't ask you for an algorithm which calculates is. I'm just looking for the name (and the correct definition) of this thing, which I call "distance"

$\endgroup$
  • $\begingroup$ It seems like you want the Edit Distance, adapted for (labelled?) graphs rather than for arbitrary strings. $\endgroup$ – hardmath Dec 26 '15 at 22:35
4
$\begingroup$

You're probably looking for graph edit distance. This has actually been discussed on stackoverflow.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.