Graph theoretic clique relaxations and applications

Balabhaskar Balasundaram, Foad Mahdavi Pajouh

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

20 Scopus citations

Abstract

Cliques and graph theoretic clique relaxations are used to model clusters in graph-based data mining, where data is modeled by a graph in which an edge implies some relationship between the entities represented by its endpoints. The need for relaxations of the clique model arises in practice when dealing with massive data sets which are error prone, resulting in false or missing edges. The clique definition which requires complete pairwise adjacency in the cluster becomes overly restrictive in such situations. Graph theoretic clique relaxations address this need by relaxing structural properties of a clique in a controlled manner via user-specified parameters. This chapter surveys such clique relaxations available in the literature primarily focusing on polyhedral results, complexity studies, approximability, and exact algorithmic approaches.

Original languageEnglish
Title of host publicationHandbook of Combinatorial Optimization
Pages1559-1598
Number of pages40
Volume3-5
ISBN (Electronic)9781441979971
DOIs
StatePublished - 1 Jan 2013

Fingerprint

Dive into the research topics of 'Graph theoretic clique relaxations and applications'. Together they form a unique fingerprint.

Cite this