I was trying to code the Ullman subgraph isomorphism agorithm. With respect to the Ullman subgraph isomorphism, there are two matrices, M and M'. How is M' being formed from M?

Matrices M' are generated by systematically changing to 0 all but one of the l's in each of the rows of 0 M, subject to the definitory condition that no column of a matrix M' may contain more than one 1.

Now what i am not able to understand this line. They have said convert all elements to zero except one 1 and also each column must not have more than one 1. In order to make each column contain only one 1, more than one 1 needs to be changed to zero right? In short can anyone explain these lines clearly with an example?

  • 2
    $\begingroup$ Are you asking to have the algorithm explained to you? $\endgroup$ – Raphael Nov 14 '15 at 15:17
  • 1
    $\begingroup$ just a small part of it. Just the condition 1 part $\endgroup$ – girl101 Nov 15 '15 at 3:36
  • 1
    $\begingroup$ Since people may not be able to access the paper (I know I'm being paywalled at home), you may want to cite the condition you need explained. $\endgroup$ – Raphael Nov 15 '15 at 9:41
  • $\begingroup$ now the paper is accessible $\endgroup$ – girl101 Nov 15 '15 at 12:30

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.