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 language | English (US) |
---|---|
Pages (from-to) | 571-596 |
Number of pages | 26 |
Journal | Computational Management Science |
Volume | 13 |
Issue number | 4 |
DOIs | |
State | Published - Oct 1 2016 |
Externally published | Yes |
Keywords
- Edge-connected subgraph
- Graph connectivity
- Integer programming
- Minimum spanning tree
- Valid inequalities
ASJC Scopus subject areas
- Management Information Systems
- Information Systems