Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked

Re^2: decomposing binary matrices

by hv (Parson)
on Feb 16, 2007 at 14:56 UTC ( #600448=note: print w/replies, xml ) Need Help??

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.


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.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://600448]
[1nickt]: ambrus I agree. I suspect one's eyes are always trying to adjust across the boundary between very bright and very dark ... like a camera's autofocus struggling to choose the target.

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (11)
As of 2017-03-27 14:02 GMT
Find Nodes?
    Voting Booth?
    Should Pluto Get Its Planethood Back?

    Results (320 votes). Check out past polls.