Name
Abstract | ||
|---|---|---|
Motivated by applications in network epidemiology, we consider the problem of determining whether it is possible to delete at most k edges from a given input graph (of small treewidth) so that the maximum component size in the resulting graph is at most h. While this problem is NP-complete in general, we provide evidence that many of the real-world networks of interest are likely to have small treewidth, and we describe an algorithm which solves the problem in time O((wh)(2w)n) on an input graph having n vertices and whose treewidth is bounded by a fixed constant w. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-319-26626-8_42 | COMBINATORIAL OPTIMIZATION AND APPLICATIONS, (COCOA 2015) |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Tree-depth,Partial k-tree,Computer science,Tree decomposition,Clique-sum,Clique-width,Treewidth,Graph minor,1-planar graph | Journal | 9486 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
8 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jessica Enright | 1 | 8 | 3.89 |
| Kitty Meeks | 2 | 10 | 2.25 |