Conference Paper (published)
Details
Citation
Enright J & Meeks K (2015) Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth. In: Lu Z, Kim D, Wu W, Li W & Du D-Z D (eds.) Combinatorial Optimization and Applications: 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings. Lecture Notes in Computer Science, 0302-9743. Combinatorial Optimization and Applications - 9th International Conference, Houston, Texas, 18.12.2015-20.12.2015. Cham, Switzerland: Springer, pp. 574-585. https://doi.org/10.1007/978-3-319-26626-8_42
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)2wn)?on an input graph having n vertices and whose treewidth is bounded by a fixed constant w.
| Status | Published |
|---|---|
| Title of series | Lecture Notes in Computer Science |
| Number in series | 0302-9743 |
| Publication date | 31/12/2015 |
| Publication date online | 31/12/2015 |
| URL | |
| Publisher | Springer |
| Place of publication | Cham, Switzerland |
| ISSN of series | 9486 |
| ISBN | 978-3-319-26625-1 |
| Conference | Combinatorial Optimization and Applications - 9th International Conference |
| Conference location | Houston, Texas |
| Dates | – |