XP is just a number  
PerlMonks 
Re^2: decomposing binary matricesby hv (Parson) 
on Feb 16, 2007 at 14:56 UTC ( #600448=note: print w/ replies, xml )  Need Help?? 
Thanks, I tried drawing the graph on a piece of paper, and while I'm not yet sure I think it may be possible to say that: the graph for any undecomposable submatrix has a cycle that traverses all its nodes; and that: the nodes in the longest cycle form the largest undecomposable submatrix. Thus from the example in the OP, you can get cycles A2E4A and B3C1D5B, but there is no cycle looping through all 10 of the nodes. That does not immediately help, since Graph will only find "the first cycle"  I can't tell from the docs (nor from a brief look at the code), but I suspect that since all my edges are undirected, it will just immediately return (eg) A2A as a cycle  but this concept may well help me search for an algorithm. Update: this page tells me: Finding the longest cycle in a graph includes the special case of Hamiltonian cycle (see gif), so it is NPcomplete.Damn. Hugo
In Section
Seekers of Perl Wisdom

