**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**10

# Search results for: Clique

##### 10 A Deterministic Polynomial-time Algorithm for the Clique Problem and the Equality of P and NP Complexity Classes

**Authors:**
Zohreh O. Akbari

**Abstract:**

**Keywords:**
Clique problem,
Deterministic Polynomial-time
Algorithm,
Equality of P and NP Complexity Classes.

##### 9 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:**
Maximum clique,
local search,
heuristic,
NP-complete.

##### 8 Some Improvements on Kumlander-s Maximum Weight Clique Extraction Algorithm

**Authors:**
Satoshi Shimizu,
Kazuaki Yamaguchi,
Toshiki Saitoh,
Sumio Masuda

**Abstract:**

Some fast exact algorithms for the maximum weight clique problem have been proposed. Östergard’s algorithm is one of them. Kumlander says his algorithm is faster than it. But we confirmed that the straightforwardly implemented Kumlander’s algorithm is slower than O¨ sterga˚rd’s algorithm. We propose some improvements on Kumlander’s algorithm.

**Keywords:**
Maximum weight clique,
exact algorithm,
branch-andbound,
NP-hard.

##### 7 Clique and Clan Analysis of Patient-Sharing Physician Collaborations

**Authors:**
Shahadat Uddin,
Md Ekramul Hossain,
Arif Khan

**Abstract:**

The collaboration among physicians during episodes of care for a hospitalised patient has a significant contribution towards effective health outcome. This research aims at improving this health outcome by analysing the attributes of patient-sharing physician collaboration network (PCN) on hospital data. To accomplish this goal, we present a research framework that explores the impact of several types of attributes (such as clique and clan) of PCN on hospitalisation cost and hospital length of stay. We use electronic health insurance claim dataset to construct and explore PCNs. Each PCN is categorised as ‘low’ and ‘high’ in terms of hospitalisation cost and length of stay. The results from the proposed model show that the clique and clan of PCNs affect the hospitalisation cost and length of stay. The clique and clan of PCNs show the difference between ‘low’ and ‘high’ PCNs in terms of hospitalisation cost and length of stay. The findings and insights from this research can potentially help the healthcare stakeholders to better formulate the policy in order to improve quality of care while reducing cost.

**Keywords:**
Clique,
clan,
electronic health records,
physician collaboration.

##### 6 Maximum Common Substructure Extraction in RNA Secondary Structures Using Clique Detection Approach

**Authors:**
Shih-Yi Chao

**Abstract:**

**Keywords:**
Clique detection,
labeled vertices,
RNA secondary
structures,
subgraph,
similarity.

##### 5 Image Modeling Using Gibbs-Markov Random Field and Support Vector Machines Algorithm

**Authors:**
Refaat M Mohamed,
Ayman El-Baz,
Aly A. Farag

**Abstract:**

**Keywords:**
Image Modeling,
MRF,
Parameters Estimation,
SVM Learning.

##### 4 Delay Preserving Substructures in Wireless Networks Using Edge Difference between a Graph and its Square Graph

**Authors:**
T. N. Janakiraman,
J. Janet Lourds Rani

**Abstract:**

**Keywords:**
Clique,
cycles,
delay preserving substructures,
maximal connected sub graph.

##### 3 Computational Identification of Bacterial Communities

**Authors:**
Eleftheria Tzamali,
Panayiota Poirazi,
Ioannis G. Tollis,
Martin Reczko

**Abstract:**

Stable bacterial polymorphism on a single limiting resource may appear if between the evolved strains metabolic interactions take place that allow the exchange of essential nutrients [8]. Towards an attempt to predict the possible outcome of longrunning evolution experiments, a network based on the metabolic capabilities of homogeneous populations of every single gene knockout strain (nodes) of the bacterium E. coli is reconstructed. Potential metabolic interactions (edges) are allowed only between strains of different metabolic capabilities. Bacterial communities are determined by finding cliques in this network. Growth of the emerged hypothetical bacterial communities is simulated by extending the metabolic flux balance analysis model of Varma et al [2] to embody heterogeneous cell population growth in a mutual environment. Results from aerobic growth on 10 different carbon sources are presented. The upper bounds of the diversity that can emerge from single-cloned populations of E. coli such as the number of strains that appears to metabolically differ from most strains (highly connected nodes), the maximum clique size as well as the number of all the possible communities are determined. Certain single gene deletions are identified to consistently participate in our hypothetical bacterial communities under most environmental conditions implying a pattern of growth-condition- invariant strains with similar metabolic effects. Moreover, evaluation of all the hypothetical bacterial communities under growth on pyruvate reveals heterogeneous populations that can exhibit superior growth performance when compared to the performance of the homogeneous wild-type population.

**Keywords:**
Bacterial polymorphism,
clique identification,
dynamic FBA,
evolution,
metabolic interactions.

##### 2 Analysis of Social Network Using Clever Ant Colony Metaphor

**Authors:**
Mohammad Al-Fayoumi,
Soumya Banerjee,
Jr.,
P. K. Mahanti

**Abstract:**

A social network is a set of people or organization or other social entities connected by some form of relationships. Analysis of social network broadly elaborates visual and mathematical representation of that relationship. Web can also be considered as a social network. This paper presents an innovative approach to analyze a social network using a variant of existing ant colony optimization algorithm called as Clever Ant Colony Metaphor. Experiments are performed and interesting findings and observations have been inferred based on the proposed model.

**Keywords:**
Social Network,
Ant Colony,
Maximum Clique,
Sub
graph,
Clever Ant colony.

##### 1 Natural Emergence of a Core Structure in Networks via Clique Percolation

**Authors:**
A. Melka,
N. Slater,
A. Mualem,
Y. Louzoun

**Abstract:**

**Keywords:**
Networks,
cliques,
percolation,
core structure,
phase
transition.