PhD Studentships: Node and Edge Deletion Problems in Networks

Strathclyde Business School

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.
For more information please click here.
Candidate Requirements
- 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)

Funding information

Value:

£14,296 (pa for 3 years)

Funding applies to:

Open to applicants from a range of countries

Contacts and how to apply

Academic contact:

Informal enquiries to Dr Kerem Akartunali (kerem.akartunali@strath.ac.uk) or Dr Ashwin Arulselvan (ashwin.arulselvan@strath.ac.uk), Department of Management Science.

Administrative contact and how to apply:

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

Application deadline:

31 May 2016