[GAP Forum] a graph question
dima at thi.informatik.uni-frankfurt.de
Wed Jun 16 00:37:31 BST 2004
Dear GAP forum,
On Tue, Jun 15, 2004 at 12:48:07PM +0100, Petra Holmes wrote:
> I have a graph on about 25000 points. I would like to find the size of a
> maximal set of pairwise non-adjacent points. Is there a way to do this in
that's an NP-hard problem, moreover, a
one that is hard to approximate. Unless the graph is very dence, you might be
seriously out of luck, no matter what software you're using.
You might have to combine information about co-cliques you know
with upper bounds on their size, such as one can obtain from
the information on the graph spectrum, etc...
More information about the Forum