Deleting edges to restrict the size of an epidemic: a new application for treewidth
- Submitting institution
-
University of Glasgow
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 11-00947
- Type
- D - Journal article
- DOI
-
10.1007/s00453-017-0311-7
- Title of journal
- Algorithmica
- Article number
- -
- First page
- 1857
- Volume
- 80
- Issue
- 6
- ISSN
- 0178-4617
- Open access status
- Compliant
- Month of publication
- June
- Year of publication
- 2018
- URL
-
http://eprints.gla.ac.uk/139650/
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
1
- Research group(s)
-
-
- Citation count
- 1
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- ORIGINALITY: We show that many graph modification problems can be solved efficiently on graphs with small treewidth. While treewidth is popular within parameterised complexity mainly for its theoretical properties, here we find that it is a realistic parameter for our application-relevant dataset. SIGNIFICANCE: We demonstrate empirically that this approach is effective for identifying the optimal contacts to forbid within Scotland's cattle trade network in order to restrict the size of epidemics. A conference version (in COCOA 2015) acted as "proof of concept" for a Royal Society of Edinburgh Personal Research Fellowship (worth £290K). RIGOUR: All theoretical results are proven mathematically.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -