misleading/wrong documentation for package graphs



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/