Parameterized Complexity of Network Design Problems

Pranabendu Mirsa

Affiliation:

Department of Informatics
University of Bergen
Norway

Time:

Thursday, 10 January 2019, 14:30 to 15:30

Venue:

• A-201 (STCS Seminar Room)

Organisers:

Abstract:  Network Design Problems, which concern designing minimum cost networks that satisfy given set of connectivity constrains'', are very well studied in computer science and combinatorial optimization. Almost all these problems are NP-hard, and a number of results are known about them in the realm of approximation algorithms. Parameterized Complexity is a different framework for dealing with computational intractability, where typically we try to design fast algorithms to solve the problem on those instances which admit a small cost solution''. In this talk we will look at some recent results on the parameterized complexity of network design problems, and future directions for research.