BannerDM1400x300

PhD Seminar on Combinatorics, Games and Optimisation

Below you'll find the program for the PhD Seminar on Combinatorics, Games and Optimisation (formally known as the Lunchtime Seminar: 2006-2016). The Seminar normally takes place on Fridays from 12.00 pm - 1.30 pm in room 32L.B.09 (32 Lincoln's Inn Fields, LSE).

Questions, suggestions, etc., about the seminar can be forwarded to the seminar administrator, by sending an e-mail to: seminar@maths.lse.ac.uk

Upcoming Speakers:

Friday 19 January
No seminar

Friday 26 January
Speaker, title and abstract TBC

Friday 2 February
Speaker, title and abstract TBC

Friday 9 February
Speaker, title and abstract TBC

Friday 16 February
Speaker, title and abstract TBC

Friday 23 February
Speaker, title and abstract TBC

Friday 2 March
Speaker, title and abstract TBC

Friday 9 March
Speaker, title and abstract TBC

Friday 16 March
Speaker, title and abstract TBC

Friday 23 March
Speaker, title and abstract TBC

Previous seminars in this series: 

Lent Term 2018

Friday 12 January - Stanislav Kučera (LSE)
Simultaneous Minimum Spanning Trees

Simultaneous Embedding with Fixed Edges (SEFE) is a problem where given k planar graphs we ask whether they can be simultaneously embedded so that the embedding of each graph is planar and common edges are drawn the same. Problems of SEFE type have inspired questions of Simultaneous Geometrical Representations and further derivations. Based on this motivation we investigate the generalisation of the simultaneous paradigm on the classical combinatorial problem of minimum spanning trees. Given k graphs with weighted edges, such that they have a common intersection, are there minimum spanning trees of the respective graphs such that they agree on the intersection? We show that the unweighted case is polynomial-time solvable while the weighted case is only polynomial-time solvable for k=2 and it is NP-complete for k>2.

2017, 2016, 2015, 2014, 2013, 2012