Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

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

IndependetVertexSetQ Bug

Back to article view | Back to comp.soft-sys.math.mathematica

Contents

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

#1435 — IndependetVertexSetQ Bug

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

[toc] | [standalone]

Back to top | Article view | comp.soft-sys.math.mathematica

csiph-web