TY - JOUR
T1 - Integer programming formulations for minimum spanning forests and connected components in sparse graphs
AU - Fan, Neng
AU - Golari, Mehdi
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2014.
PY - 2014
Y1 - 2014
N2 - In this paper, we first review several integer programming formulations for the minimum spanning tree problem, and then adapt these formulations for solving the minimum spanning forest problem in sparse graphs. Some properties for the spanning forest and connected components are studied, and then we present the integer programming formulation for finding the largest connected component, which has been widely used for network vulnerability analysis.
AB - In this paper, we first review several integer programming formulations for the minimum spanning tree problem, and then adapt these formulations for solving the minimum spanning forest problem in sparse graphs. Some properties for the spanning forest and connected components are studied, and then we present the integer programming formulation for finding the largest connected component, which has been widely used for network vulnerability analysis.
KW - Connected components
KW - Integer programming
KW - Minimum spanning forest
KW - Minimum spanning tree
KW - Network vulnerability analysis
UR - http://www.scopus.com/inward/record.url?scp=84921498294&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84921498294&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-12691-3_46
DO - 10.1007/978-3-319-12691-3_46
M3 - Article
AN - SCOPUS:84921498294
SN - 0302-9743
VL - 8881
SP - 613
EP - 622
JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ER -