On the minimum-cost $$\lambda $$ λ -edge-connected k-subgraph problem

Elham Sadeghi and Neng Fan ()
Additional contact information
Elham Sadeghi: University of Arizona
Neng Fan: University of Arizona

Computational Management Science, 2016, vol. 13, issue 4, No 4, 596 pages

Abstract: Abstract In this paper, we propose several integer programming (IP) formulations to exactly solve the minimum-cost $$\lambda $$ λ -edge-connected k-subgraph problem, or the $$(k,\lambda )$$ ( k , λ ) -subgraph problem, based on its graph properties. Special cases of this problem include the well-known k-minimum spanning tree problem (if $$\lambda =1$$ λ = 1 ), $$\lambda $$ λ -edge-connected spanning subgraph problem (if $$k=|V|$$ k = | V | ) and k-clique problem (if $$\lambda = k-1$$ λ = 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,\lambda )$$ ( 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.

Keywords: Edge-connected subgraph; Minimum spanning tree; Integer programming; Graph connectivity; Valid inequalities (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10287-016-0260-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:comgts:v:13:y:2016:i:4:d:10.1007_s10287-016-0260-7

Ordering information: This journal article can be ordered from
http://www.springer. ... ch/journal/10287/PS2

DOI: 10.1007/s10287-016-0260-7

Access Statistics for this article

Computational Management Science is currently edited by Ruediger Schultz

More articles in Computational Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().