MathGroup Archive 2011

[Date Index] [Thread Index] [Author Index]

Search the Archive

IndependetVertexSetQ Bug

  • To: mathgroup at smc.vnet.net
  • Subject: [mg117898] IndependetVertexSetQ Bug
  • From: Eduardo F <eduardofeo at gmail.com>
  • Date: Sat, 2 Apr 2011 17:06:31 -0500 (EST)

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


  • Prev by Date: Re: Wolfram, meet Stefan and Boltzmann
  • Next by Date: Re: Fit Gaussian function to histogram
  • Previous by thread: Re: SumConvergence mistake?
  • Next by thread: Damaged Palettes in 8.0 and 8.0.1