> < ^ From:

< ^ Subject:

Dear Gap Forum,

Chris Charnes recently asked:

I would like to know (refrence?) what algorithms

GRAPE uses to find complete subgraphs with side conditions of a given graph.

At present the only reference for the GRAPE functions

'CompleteSubgraphs' and 'CompleteSubgraphsOfGivenSize' is the GAP

manual and the GRAPE library source code. Of the two functions,

'CompleteSubgraphsOfGivenSize' is the more sophisticated, and should be

used if at all possible.

I'm not sure what you mean by 'side conditions of a given graph'.

'CompleteSubgraphsOfGivenSize' finds complete subgraphs of a given size

(surprise surprise), and is controlled in its search and output by the

parameters as documented. 'CompleteSubgraphs' can also be used to

find complete subgraphs of a given size (but is not as good as

'CompleteSubgraphsOfGivenSize') or to find maximal complete subgraphs.

Again, you should read the documentation to see how to control this

(less sophisticated) function.

I am developing a new version of 'CompleteSubgraphsOfGivenSize'

which has the following features:

(1) It allows you to assign integer weights to the vertices

of the input graph, gamma (the weight of a vertex must be

preserved by gamma.group) and then the *size* of a complete

subgraph (to be found) is the sum of the weights of its vertices.

Thus, the new version does the same as the old when each vertex

has weight 1 (the default).(2) It has more thorough documentation than the old version.

(3) It is slightly easier to control.

If you would like a copy of this new (experimental) version,

then I would be happy to send it to you, but would like to

be informed how things go with it. Eventually, I plan

to write a paper on the ideas and algorithms behind this

new function.

Best regards, Leonard.

> < [top]