Subject: misleading/wrong documentation for package graphs
From: Oliver Kullmann
Date: Tue, 26 Feb 2008 15:52:48 +0000
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/