Abstract
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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 613-622 |
| Number of pages | 10 |
| Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
| Volume | 8881 |
| DOIs | |
| State | Published - 2014 |
Keywords
- Connected components
- Integer programming
- Minimum spanning forest
- Minimum spanning tree
- Network vulnerability analysis
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)