Are there known algorithms for the isomorphism problem for directed weighted multigraphs? If not, could one be created simply by adapting existing algorithms for graphs or digraphs, or is it entirely non-obvious?

  • $\begingroup$ Your problem is likely GI-complete. I suggest taking a look at some examples of reducing fancy variants of graph isomorphism to the classical setting. $\endgroup$ – Yuval Filmus May 31 '19 at 6:37
  • $\begingroup$ @YuvalFilmus So is there no "direct" result on this particular problem, but one is supposed to be able to figure out an adaptation by himself? $\endgroup$ – apen May 31 '19 at 17:58
  • $\begingroup$ You can adapt the Weisfeiler-Lehman approach. $\endgroup$ – Yuval Filmus May 31 '19 at 18:07

Your Answer

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

Browse other questions tagged or ask your own question.