Groups > comp.soft-sys.math.mathematica > #1435

IndependetVertexSetQ Bug

From	Eduardo F <eduardofeo@gmail.com>
Newsgroups	comp.soft-sys.math.mathematica
Subject	IndependetVertexSetQ Bug
Date	2011-04-02 22:06 +0000
Organization	Steven M. Christensen and Associates, Inc and MathTensor, Inc.
Message-ID	<in86kv$9uv$1@smc.vnet.net> (permalink)

Show all headers | View raw

Hello

I have found what seems to be a bug inside the implementation of
IndependetVertexSetQ predicate. I realized it after using this
predicate inside my code thousands of times, which caused the computer
to run out of memory.
Using an alternative definition, and comparing the time it takes to
compute, it is clear that something is not right inside the provided
implementation. I'm using Mathematica 8.0.

G = RandomGraph[{16, 20}];
S = Cases[Subsets[VertexList[G]], Except[{}]];
MyIndependentVertexSetQ[g_, s_] :=
  Length[EdgeList[Subgraph[g, s]]] == 0;


Timing[T1 = Table[IndependentVertexSetQ[G, s], {s, S}];]
{19.81000000000001`, Null}

Timing[T2  = Table[MyIndependentVertexSetQ[G, s], {s, S}];]
{2.5900000000000034`, Null}

T1 == T2
True

Best Regards

Eduardo Feo

Back to comp.soft-sys.math.mathematica | Previous | Next | Find similar | Unroll thread

Thread

IndependetVertexSetQ Bug Eduardo F <eduardofeo@gmail.com> - 2011-04-02 22:06 +0000

csiph-web