http://qs321.pair.com?node_id=600448


in reply to Re: decomposing binary matrices
in thread decomposing binary matrices

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 A-2-E-4-A and B-3-C-1-D-5-B, 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) A-2-A 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 NP-complete.
Damn.

Hugo

Replies are listed 'Best First'.
Re^3: decomposing binary matrices
by Herkum (Parson) on Feb 16, 2007 at 16:58 UTC

    That was the reason I suggested the Mastering Algorithms with Perl book. It dealt quite a few algorithms and devotes a chapter to matrices. It also goes into great detail for several different methods for using Graph.

    Graph by itself is not very useful because it is expected that you know what your are doing, which I find frustrating when I encounter a problem. But there is a lot more to it than first appearances would suggest.