**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**5

# NP-complete Related Publications

##### 5 A New Effective Local Search Heuristic for the Maximum Clique Problem

**Authors:**
S. Balaji

**Abstract:**

An edge based local search algorithm, called ELS, is proposed for the maximum clique problem (MCP), a well-known combinatorial optimization problem. ELS is a two phased local search method effectively £nds the near optimal solutions for the MCP. A parameter ’support’ of vertices de£ned in the ELS greatly reduces the more number of random selections among vertices and also the number of iterations and running times. Computational results on BHOSLIB and DIMACS benchmark graphs indicate that ELS is capable of achieving state-of-the-art-performance for the maximum clique with reasonable average running times.

**Keywords:**
heuristic,
local search,
NP-complete,
Maximum clique

##### 4 Equivalence Class Subset Algorithm

**Authors:**
Jeffrey L. Duffany

**Abstract:**

**Keywords:**
Algorithm,
Complexity,
NP-complete

##### 3 Optimal Solution of Constraint Satisfaction Problems

**Authors:**
Jeffrey L. Duffany

**Abstract:**

**Keywords:**
Algorithm,
Complexity,
constraint,
NP-complete

##### 2 An Alternative Proof for the NP-completeness of Top Right Access point-Minimum Length Corridor Problem

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

**Abstract:**

In the Top Right Access point Minimum Length Corridor (TRA-MLC) problem [1], a rectangular boundary partitioned into rectilinear polygons is given and the problem is to find a corridor of least total length and it must include the top right corner of the outer rectangular boundary. A corridor is a tree containing a set of line segments lying along the outer rectangular boundary and/or on the boundary of the rectilinear polygons. The corridor must contain at least one point from the boundaries of the outer rectangle and also the rectilinear polygons. Gutierrez and Gonzalez [1] proved that the MLC problem, along with some of its restricted versions and variants, are NP-complete. In this paper, we give a shorter proof of NP-Completeness of TRA-MLC by findig the reduction in the following way.

**Keywords:**
NP-complete,
Grid embedding of a plane graph

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

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

**Abstract:**

**Keywords:**
block,
NP-complete,
cut vertex