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 $$Owh^{2w}n$$Owh2wn on an input graph having n vertices and whose treewidth is bounded by a fixed constant w. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s00453-017-0311-7 | Algorithmica |
Keywords | DocType | Volume |
Edge-deletion,Treewidth,Network epidemiology,Graph contagion | Journal | 80 |
Issue | ISSN | Citations |
6 | 0178-4617 | 2 |
PageRank | References | Authors |
0.37 | 13 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jessica Enright | 1 | 8 | 3.89 |
| Kitty Meeks | 2 | 44 | 8.20 |