Flows and Cuts in Time-Varying Networks
Prof T Erlebach
Dr M Hoffman
No more applications being accepted
Competition Funded PhD Project (Students Worldwide)
In many settings, networks are not static but change over time: For example, links in a wireless network with mobile nodes appear and disappear, friendship relations in social networks change over time, and transport links in a public transportation network are only available at certain times. The study of graphs and networks that change over time has received increasing attention in the last few years, and efforts to adapt concepts and methods from the classical area of graph theory to time-varying graphs are under way.
In this project we will investigate temporal analogues of the classical concepts of flows and cuts in networks. How can one send as much flow as possible from one node of a temporal network to another? What is the smallest number of nodes or links that have to be disabled in order to block all temporal paths from a given source to a given destination?
Recent results have determined the complexity of the problem of computing temporal separators in various special classes of temporal graphs, and in this project we aim to study the approximability of temporal cut and flow problems. For NP-hard problem variants, we aim to develop approximation algorithms that are guaranteed to provide solutions that are provably close to the optimum, and to prove inapproximability results showing that approximations beyond a certain threshold cannot be achieved in polynomial time unless P=NP (where P is the class of decision problems that can be solved deterministically in polynomial time, and NP is the class of decision problems that can be solved in polynomial time by a non-deterministic Turing machine).
Entry requirements Applicants are required to hold/or expect to obtain a UK Bachelor Degree 2:1 or better in a relevant subject. The University of Leicester English language requirements apply where applicable.
How to apply The online application and supporting documents are due by Monday 21st January 2019.
Any applications submitted after the deadline will not be accepted for the studentship scheme.
References should arrive no later than Monday 28th January 2019.
Applicants are advised to apply well in advance of the deadline, so that we can let you know if anything is missing from your application.
1. Online application form
2. Two academic references
4. Degree certificate/s (if awarded)
5. Curriculum Vitae
6. CSE Studentship Form
7. English language qualification
Applications which are not complete by the deadline will not be considered for the studentship scheme. It is the responsibility of the applicant to ensure the application form and documents are received by the relevant deadlines.
All applications must be submitted online, along with the supporting documents as per the instructions on the website.
Please ensure that all email addresses, for yourself and your referees, are correct on the application form.
Project / Funding Enquiries Application enquiries to [Email Address Removed]
Closing date for applications – 21st January 2019
This research project is one of a number of projects in the College of Science and Engineering. It is in competition for funding with one or more of these projects. Usually the project that receives the best applicant will be awarded the funding.
This project is eligible for a fully funded College of Science and Engineering studentship that includes:
• A full UK/EU fee waiver for 3.5 years
• An annual tax free stipend of £14,777 (2018/19)
• Research Training Support Grant (RTSG)
This project is eligible for a College of Science and Engineering studentship that includes:
• A full international fee waiver for 3.5 years
• Research Training Support Grant (RTSG)
International candidates must be able to fund their living costs for the duration of the studentship.
1. Thomas Erlebach, Michael Hoffmann, Frank Kammer: On Temporal Graph Exploration. In: Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP 2015). LNCS 9134, Springer, 2015, pp. 444-455.
2. Philipp Zschoche, Till Fluschnik, Hendrik Molter, Rolf Niedermeier: The Complexity of Finding Small Separators in Temporal Graphs. In: Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Leibniz International Proceedings in Informatics (LIPIcs), 2018, pp. 45:1-45:17.
3. Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Philipp Zschoche: Temporal Graph Classes: A View Through Temporal Separators. In: Proceedings of the 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018), LNCS 11159, Springer, 2018, pp. 216-227.