Re: Finding the Maximum Number of Node-disjoint Cycles
From: Sterten (sterten_at_aol.com)
Date: 12/17/03
- Next message: Machine Learning for Signal Processing 2004 : "Machine Learning for Signal Processing 2004"
- Previous message: Michael N. Christoff: "Re: Turing-recognizable (or recursively enumerable) and Turing-decidable (or recursive) Languages"
- In reply to: Glenn C. Rhoads: "Re: Finding the Maximum Number of Node-disjoint Cycles"
- Next in thread: Glenn C. Rhoads: "Re: Finding the Maximum Number of Node-disjoint Cycles"
- Reply: Glenn C. Rhoads: "Re: Finding the Maximum Number of Node-disjoint Cycles"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 17 Dec 2003 12:18:16 GMT
>You already have come code to do this?! That would be great if I could
>use it (with attribution of course). I would have to make up any test
>cases by hand. What format should I use to describe the graph?
I have a BASIC program to find and store the holes,
generate the files, coordinate the formats,
interpret+store the output, process all the
mesh-graphs one after the other.
It calls a C-program (executable) as child-process to find a maximum
clique in the resulting intersection graph.
This could all be done in one single program and the BASIC program
can be converted to C,but it's a bit tedious. Maybe you want to do it ? ;-)
I'd like to make a single C-program, which finds the
maximum disjoint cycles(holes) in any graph -
but only if it's not too much work ;-)
I'd also like to improve input/output , stack-usage ,
so it can handle very big graphs.
mesh6 with 4832 holes was solved in a few seconds but on mesh7
with 80302 holes I got an exception after some minutes :-(
best graph-file-format IMO is : just the n*n values of the
adjacency matrix in one line with or without blanks.
You can put many graphs of different sizes into one file.
The program reads all characters ,ignoring blanks, into one line
until it finds an end-of-line-character , then calculates
n = sqrt(characters in line) and converts the line into a n*n matrix.
I don't use bit-vectors (except for these large intersection graphs),
memory is big and cheap these days.
Of course, in principle it's easy to read and convert other formats.
BTW. does somebody know of a universal program which reads/converts
all known graph-formats ?
>> ... provided you find nothing better with the bipartite-matching
>> idea or such. I have no clue there.
>
>I think I found what I was thinking of. From a bipartite graph G,
>there is a way to construct a larger bipartite graph H such that
>G has a disjoint cycle cover if and only if H has a perfect matching.
>You should be able to convert a maximum matching on H to a maximum
>collection of disjoint cycles plus other edges on G. But this may
>not be an improvement -- H will have over 4 times as many vertices.
>Also constructing H and mapping the matching back to edges in G
>may be a pain to implement.
>
>I also found an LP relaxation of the disjoint cycle cover problem
>whose solutions are guaranteed to have integral values for all
>variables (at least for bipartite graphs, perhaps general graphs too
>but I have to check on that). Assign a variable to each edge whose
>values must satisfy the contraint of being >= 0 and = 1 (0 means edge
>is absent, 1 means edge is included). For each vertex, the sum of the
>variables corresponding to incident edges must be = 2. The objective
>function is simply the sum of the variables. So solving this LP should
>identify a maximal set of disjoint cycles (and partition the rest of
>the graph into disjoint paths). But again if this is any better.
maximize SUM {i,j} x(i,j)
with :
1 > = x(i,j) > = 1
x(i,j) = 0 , if there is no edge i--j
2 >= SUM {j} x(i,j) for all i
the maximums achieved have x(i,j) = 0 or 1 and those with
x(i,j)=1 make the edges of a max-cycle-cover (plus some other disconnected
paths)
correct ?
- Next message: Machine Learning for Signal Processing 2004 : "Machine Learning for Signal Processing 2004"
- Previous message: Michael N. Christoff: "Re: Turing-recognizable (or recursively enumerable) and Turing-decidable (or recursive) Languages"
- In reply to: Glenn C. Rhoads: "Re: Finding the Maximum Number of Node-disjoint Cycles"
- Next in thread: Glenn C. Rhoads: "Re: Finding the Maximum Number of Node-disjoint Cycles"
- Reply: Glenn C. Rhoads: "Re: Finding the Maximum Number of Node-disjoint Cycles"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
