Node and Edge Deletion Problems in Networks

  • Number of scholarships 1
  • Value £14,296 (pa for 3 years)
  • Opens 4 February 2016
  • Deadline 31 May 2016
  • Help with Tuition fees, Living costs
  • Duration 36 months

Eligibility

This PhD project requires a highly numerate graduate with skills and interests in computational science. Candidates should have at least a strong Honours degree or equivalent (a strong 2:1 Honours degree, or an undergraduate degree with 3.3 GPA in a 4.0 system), or preferably a Master’s degree in a quantitative discipline such as industrial engineering, operations research, mathematics or computer science (amongst others). Candidates who are not native English speakers will be required to provide evidence for their English skills (such as by IELTS or similar tests that are approved by UKVI, or a degree completed in an English speaking country)

Project Details

In this project, we plan to develop efficient algorithms to study the node and edge deletion problems on networks. These problems stem from various important applications in energy networks (e.g., how to build a network that can survive failures on particular power lines), epidemic containment (e.g., how to ensure disconnectivity between various populations) and defense operations (e.g., where to focus attacks on enemy to ensure faster victory). The problem involves in effectively identifying a subset of nodes or edges of a network, which on deletion results in a subgraph with desirable properties. Some of the properties of interest include the connectivity in the graph, a restrictive size of the largest component, and denseness of the components formed.

As part of the research, we plan to establish theoretical and empirical analysis for two specific network types. The theoretical work might include methods such as complexity analysis, analysis of the hardness of approximation and developing approximation algorithms and polyhedral analysis for the problems. The experimental work might involve designing and implementing exact computational integer programs and efficient heuristics that would be built upon the theoretical foundation.

How to apply

Candidates are expected to submit a cover letter, a research proposal detailing their 3-year plan, CV, any university degree certificates and transcripts, English test results (if applicable), two recommendation letters (or contact details of two referees, if letters are not available to them), and any other supporting documents. 

Applications to: Alison Kerr (alison.kerr@strath.ac.uk)