Integer Programming Formulations for Minimum Spanning Forests and Connected Components in Sparse Graphs

被引：5

作者：

Fan, Neng ^{[1
]}

Golari, Mehdi ^{[1
]}

机构：

[1] Univ Arizona, Dept Syst & Ind Engn, Tucson, AZ 85721 USA

来源：

COMBINATORIAL OPTIMIZATION AND APPLICATIONS (COCOA 2014) | 2014年 / 8881卷

关键词：

Minimum spanning forest; Minimum spanning tree; Connected components; Network vulnerability analysis; Integer programming; TREE PROBLEM;

D O I：

10.1007/978-3-319-12691-3_46

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：613 / 622

页数：10

共 12 条

[1] TOPOLOGY AND DATA
Carlsson, Gunnar
[J]. BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 2009, 46 (02) : 255 - 308
[2] Cole R., 1996, SPAA '96. 8th Annual ACM Symposium on Parallel Algorithms and Architectures, P243, DOI 10.1145/237502.237563
[3] Extended formulations in combinatorial optimization
Conforti, Michele
Cornuejols, Gerard
Zambelli, Giacomo
[J]. 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2010, 8 (01): : 1 - 48
[4] Edmonds J., 1971, Mathematical Programming, V1, P127, DOI DOI 10.1007/BF01584082
[5] A comparative analysis of several formulations for the generalized minimum spanning tree problem
Feremans, C
Labbé, M
Laporte, G
[J]. NETWORKS, 2002, 39 (01) : 29 - 34
[6] Kaibel V, 2010, LECT NOTES COMPUT SC, V6080, P135, DOI 10.1007/978-3-642-13036-6_11
[7] USING SEPARATION ALGORITHMS TO GENERATE MIXED INTEGER MODEL REFORMULATIONS
MARTIN, RK
[J]. OPERATIONS RESEARCH LETTERS, 1991, 10 (03) : 119 - 128
[8] ON THE GENERALIZED MINIMUM SPANNING TREE PROBLEM
MYUNG, YS
LEE, CH
TCHA, DW
[J]. NETWORKS, 1995, 26 (04) : 231 - 241
[9] Detecting Critical Nodes in Interdependent Power Networks for Vulnerability Assessment
Nguyen, Dung T.
Shen, Yilin
Thai, My T.
[J]. IEEE TRANSACTIONS ON SMART GRID, 2013, 4 (01) : 151 - 159
[10] A randomized time-work optimal parallel algorithm for finding a minimum spanning forest
Pettie, S
Ramachandran, V
[J]. SIAM JOURNAL ON COMPUTING, 2002, 31 (06) : 1879 - 1895

← 1 2 →