EconPapers    
Economics at your fingertips  
 

An analytical comparison of the LP relaxations of integer models for the k-club problem

Maria Teresa Almeida and Filipa D. Carvalho

European Journal of Operational Research, 2014, vol. 232, issue 3, 489-498

Abstract: Given an undirected graph G=(V,E), a k-club is a subset of nodes that induces a subgraph with diameter at most k. The k-club problem is to find a maximum cardinality k-club. In this study, we use a linear programming relaxation standpoint to compare integer formulations for the k-club problem. The comparisons involve formulations known from the literature and new formulations, built in different variable spaces. For the case k=3, we propose two enhanced compact formulations. From the LP relaxation standpoint these formulations dominate all other compact formulations in the literature and are equivalent to a formulation with a non-polynomial number of constraints. Also for k=3, we compare the relative strength of LP relaxations for all formulations examined in the study (new and known from the literature). Based on insights obtained from the comparative study, we devise a strengthened version of a recursive compact formulation in the literature for the k-club problem (k>1) and show how to modify one of the new formulations for the case k=3 in order to accommodate additional constraints recently proposed in the literature.

Keywords: Combinatorial optimization; Formulations; k-Clubs; Integer programming; Clique relaxations (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221713006504
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:232:y:2014:i:3:p:489-498

DOI: 10.1016/j.ejor.2013.08.004

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu (repec@elsevier.com).

 
Page updated 2024-12-28
Handle: RePEc:eee:ejores:v:232:y:2014:i:3:p:489-498