misleading/wrong documentation for package graphs

The documentation should say that functions find maximum
clique/independent set/matching. I will fix that.

The algorithm for maximum clique is a branch and bound algorithm. It
uses greedy coloring for the bound.

HTH,

Andrej

On Tue, Feb 26, 2008 at 4:52 PM, Oliver Kullmann
<O.Kullmann at swansea.ac.uk> wrote:
> Hi,
>
>  in the graphs-documentation one finds
>  --------
>  Function: max_clique (gr)
>  Returns a maximal clique of the graph gr.
>
>  Function: max_independent_set (gr)
>  Returns a maximal independent set of the graph gr.
>
>  Function: max_matching (gr)
>  Returns a maximal matching of the graph gr.
>  ---------
>
>  Now in combinatorics there is a well-established standard
>  about the use of "maximal" in this context, namely that
>  it is a subset which is maximal w.r.t. subset-inclusion.
>
>  So, this would match the above wording, since there are
>  many maximal subsets, some larger, some smaller, and
>  one can only speak of *a* maximal soandso.
>
>  On the other hand I regard this as utterly useless:
>  Just to get some maximal subset by a greedy approach
>  is pretty trivial, and especially regarding the matchings
>  obviously the user wants a *maximum* matching, a matching
>  of maximal *size*.
>
>  Now I actually hope that this is what the above functions
>  achieve, namely a clique of maximal size (or a "maximum
>  clique", but such wording would be too clever in this
>  context), etc.
>
>  And then, obviously, this should be stated in the documentation.
>
>  Since a maximum clique and a maximum independent set is a non-trivial
>  problem, it would also be good to indicate the algorithms.
>
>  Oliver
>
>  P.S. I had a quick look into the source-code, and it could either
>  be a simple brute-force method, computing a maximum subset,
>  or a simple heuristic, just computing some maximal subset.
>
>  --
>  Dr. Oliver Kullmann
>  Computer Science Department
>  Swansea University
>  Faraday Building, Singleton Park
>  Swansea SA2 8PP, UK
>  http://cs.swan.ac.uk/~csoliver/
>  _______________________________________________
>  Maxima mailing list
>  Maxima at math.utexas.edu
>  http://www.math.utexas.edu/mailman/listinfo/maxima