Details of Grant 

EPSRC Reference:	EP/F064551/1
Title:	Structural Vulnerability Measures for Networks and Graphs
Principal Investigator:	Paulusma, Professor D
Other Investigators:	Broersma, Professor H Johnson, Professor M
Researcher Co-Investigators:
Project Partners:
Department:	Engineering and Computing Sciences
Organisation:	Durham, University of
Scheme:	Standard Research
Starts:	01 April 2009	Ends:	30 September 2012	Value (£):	493,476
EPSRC Research Topic Classifications:	Fundamentals of Computing
EPSRC Industrial Sector Classifications:	No relevance to Underpinning Sectors
Related Grants:
Panel History:	Panel Date Panel Name Outcome 21 Apr 2008 ICT Prioritisation Panel (April 2008) Announced
Summary on Grant Application Form
Networks appear in many different applications and settings, the more known ones being telecommunication networks, computer networks, the internet, road and rail networks, and other logistic networks, like gas and electricity networks. In all applications of networks vulnerability and reliability are crucial and important features. From a practical point of view, in many network applications the first thing one wants to know is how well the network performs with regard to node or link failures: are the remaining nodes still connected if some of the nodes or links break down? This is captured by the concepts of connectivity and edge connectivity that are well-studied within the research area of graph theory. Due to existing knowledge from this area the level of connectivity and edge connectivity is closely related to the existence of certain sets of nodes and links that separate the network in disconnected parts, as well as to the existence of certain connecting paths between pairs of nodes. These structural results have very nice algorithmic implications, namely that the level of connectivity and edge connectivity, as well as the connecting paths between pairs of nodes can be determined by fast algorithms. So at first sight everything seems to be satisfactorily settled. However, in practice the measures connectivity and edge connectivity are too simple and too rude: they do not capture the effect of node or link failures on networks well enough. Depending on the type of application, one would like to take into account other effects of node or link failure (vertex or edge deletions), like the number of resulting components, the size of the largest (smallest) component, a split in (almost) equally sized parts, etc. In the proposed research we study various vulnerability measures that capture such effects. We will develop and extend the knowledge base for these measures by analysing their structural properties. We will also consider algorithmic aspects that will help us in answering the question how easy or difficult these measures can be computed in (large) networks. These structural and algorithmic properties of vulnerability measures can also have an impact on solving other difficult optimization problems for networks. If one can break a large network into smaller networks by deleting certain sets of nodes or links, then under some conditions the solutions for the optimization problem on the smaller networks can be combined to a solution for the optimization problem on the larger network. This approach for solving optimization problems is known as divide-and-conquer.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:
Further Information:
Organisation Website: