On the minimum-cost λ -edge-connected k-subgraph problem

Elham Sadeghi, Neng Fan

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper, we propose several integer programming (IP) formulations to exactly solve the minimum-cost λ-edge-connected k-subgraph problem, or the (k, λ) -subgraph problem, based on its graph properties. Special cases of this problem include the well-known k-minimum spanning tree problem (if λ= 1), λ-edge-connected spanning subgraph problem (if k= | V|) and k-clique problem (if λ= k- 1 and there are exact k vertices in the subgraph). As a generalization of k-minimum spanning tree and a case of the (k, λ) -subgraph problem, the (k, 2)-subgraph problem is studied, and some special graph properties are proved to find stronger and more compact IP formulations. Additionally, we study the valid inequalities for these IP formulations. Numerical experiments are performed to compare proposed IP formulations and inequalities.

Original languageEnglish (US)
Pages (from-to)571-596
Number of pages26
JournalComputational Management Science
Volume13
Issue number4
DOIs
StatePublished - Oct 1 2016
Externally publishedYes

Keywords

  • Edge-connected subgraph
  • Graph connectivity
  • Integer programming
  • Minimum spanning tree
  • Valid inequalities

ASJC Scopus subject areas

  • Management Information Systems
  • Information Systems

Fingerprint

Dive into the research topics of 'On the minimum-cost λ -edge-connected k-subgraph problem'. Together they form a unique fingerprint.

Cite this