A novel type of branch and bound for maximum independent set

Details A novel type of branch and bound for maximum independent set A novel type of branch and bound for maximum independent set

2009-01-28

arxiv.org/abs/0901.4417v2

Computer Science

Data Structures and Algorithms

The section break up in v2 is improved, parts are trimmed, other parts added (e.g graphs with up to 3000 vertices are handled)

Scientific paper

Several algorithms are presented. The standard algorithm generates all N anticliques of a graph with v vertices in time O(N^v2). It can e.g. be adapted to calculate the independence polynomial of G, to generate all maximum cardinality anticliques, or just one maximum anticlique. The latter was programmed using the Mathematica 6.0 code. For a random (45, 92)-graph G a maximum anticlique of size 21 was found in 1.344 sec, whereas the "hardwired" Mathematica command MaximumIndependentSet[G] clocked in at 155838 sec, which is five orders of magnitude slower.

Affiliated with

Also associated with

No associations

Rating

A novel type of branch and bound for maximum independent set does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A novel type of branch and bound for maximum independent set, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A novel type of branch and bound for maximum independent set will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-344564