**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**6

# Search results for: vertex cover

##### 6 An Effective Algorithm for Minimum Weighted Vertex Cover Problem

**Authors:**
S. Balaji,
V. Swaminathan,
K. Kannan

**Abstract:**

The Minimum Weighted Vertex Cover (MWVC) problem is a classic graph optimization NP - complete problem. Given an undirected graph G = (V, E) and weighting function defined on the vertex set, the minimum weighted vertex cover problem is to find a vertex set S V whose total weight is minimum subject to every edge of G has at least one end point in S. In this paper an effective algorithm, called Support Ratio Algorithm (SRA), is designed to find the minimum weighted vertex cover of a graph. Computational experiments are designed and conducted to study the performance of our proposed algorithm. Extensive simulation results show that the SRA can yield better solutions than other existing algorithms found in the literature for solving the minimum vertex cover problem.

**Keywords:**
Weighted vertex cover,
vertex support,
approximation algorithms,
NP-complete problem.

##### 5 Optimization of Unweighted Minimum Vertex Cover

**Authors:**
S. Balaji,
V. Swaminathan,
K. Kannan

**Abstract:**

**Keywords:**
vertex cover,
vertex support,
approximation algorithms,
NP - complete problem.

##### 4 Approximating Maximum Weighted Independent Set Using Vertex Support

**Authors:**
S. Balaji,
V. Swaminathan,
K. Kannan

**Abstract:**

**Keywords:**
weighted independent set,
vertex cover,
vertex support,
heuristic,
NP - hard problem.

##### 3 A Meta-Heuristic Algorithm for Vertex Covering Problem Based on Gravity

**Authors:**
S. Raja Balachandar,
K.Kannan

**Abstract:**

A new Meta heuristic approach called "Randomized gravitational emulation search algorithm (RGES)" for solving vertex covering problems has been designed. This algorithm is found upon introducing randomization concept along with the two of the four primary parameters -velocity- and -gravity- in physics. A new heuristic operator is introduced in the domain of RGES to maintain feasibility specifically for the vertex covering problem to yield best solutions. The performance of this algorithm has been evaluated on a large set of benchmark problems from OR-library. Computational results showed that the randomized gravitational emulation search algorithm - based heuristic is capable of producing high quality solutions. The performance of this heuristic when compared with other existing heuristic algorithms is found to be excellent in terms of solution quality.

**Keywords:**
Vertex covering Problem,
Velocity,
Gravitational Force,
Newton's Law,
Meta Heuristic,
Combinatorial optimization.

##### 2 Connected Vertex Cover in 2-Connected Planar Graph with Maximum Degree 4 is NP-complete

**Authors:**
Priyadarsini P. L. K,
Hemalatha T.

**Abstract:**

**Keywords:**
NP-complete,
2-Connected planar graph,
block,
cut vertex

##### 1 Combinatorial Optimisation of Worm Propagationon an Unknown Network

**Authors:**
Eric Filiol,
Edouard Franc,
Alessandro Gubbioli,
Benoit Moquet,
Guillaume Roblot

**Abstract:**

**Keywords:**
Combinatorial worm,
worm spreading,
worm virulence,
stealth worm,
spreading simulation,
vertex cover,
networktopology,
WAST simulator,
SuWAST simulator.