TY - CHAP
T1 - Graph theoretic clique relaxations and applications
AU - Balasundaram, Balabhaskar
AU - Pajouh, Foad Mahdavi
N1 - Publisher Copyright:
© Springer Science+Business Media New York 2013. All rights are reserved.
PY - 2013/1/1
Y1 - 2013/1/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84880313548&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84880313548&partnerID=8YFLogxK
U2 - 10.1007/978-1-4419-7997-1_9
DO - 10.1007/978-1-4419-7997-1_9
M3 - Chapter
AN - SCOPUS:84880313548
SN - 9781441979964
VL - 3-5
SP - 1559
EP - 1598
BT - Handbook of Combinatorial Optimization
ER -