Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask

Re^2: decomposing binary matrices (2)

by hv (Parson)
on Feb 27, 2007 at 21:01 UTC ( #602387=note: print w/replies, xml ) Need Help??

in reply to Re: decomposing binary matrices (2)
in thread decomposing binary matrices (2)

Ah yes, I think I understand - I'd looked at the perfect match algorithm before, but discarded it then because at the time I was trying to solve the splitting problem for which I needed specifically a cycle, and it looked like extending the algorithm to require a cycle was going to degenerate it into something no better than the brute force.

If I'm no longer looking for a cycle, then I can probably use that algorithm. I'll give it a go, and come back.

Update: I *do* understand now. I had read your approach as "to check the edge uv, remove the edge and check ...", but eventually worked out that couldn't be right, that I had to remove the two vertices instead.

What's more, thinking about it in the graph form it is clear to me that after cleanup the split also becomes trivial - the graph simply falls apart into disconnected subgraphs.



Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://602387]
[Lady_Aleena]: What?! Can't stat ~/Music: No such file or directory? The ~/ doesn't expand?
[Lady_Aleena]: And the env variable $HOME doesn't work either. !@#$
[shmem]: no, that's a shell feature. Use $ENV{HOME}
[marioroy]: my $ans = qx{ find \$HOME -name "*.pl" -exec ls -l {} \\; };
[marioroy]: must backslash $ inside qx
[Lady_Aleena]: I haven't written perl for a while, I've been trying to do things at the command line. I'm having to relearn a lot.
[marioroy]: LA can you post the qx find again
[Lady_Aleena]: Things I would have written a script for while I was on Windows, I can run simply on the command line.
[Lady_Aleena]: marioroy, my @music_times = qx(find ~/Music/Albums/ -type f -iname '*.mp3' -exec mp3info -p "%S\n" {} \;); #unfixed

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (11)
As of 2017-04-23 21:07 GMT
Find Nodes?
    Voting Booth?
    I'm a fool:

    Results (432 votes). Check out past polls.