Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 10.03.2016 at 12:20 in S6, there is the following noon lecture:

Parameterized complexity of length-bounded cuts (Jirka Matoušek Prize talk)

Dušan Knop

Abstract

The minimal length-bounded L-cut problem is to compute for a given integer L, a graph G, a source s and a sink t a set of edges F, such that if we remove all edges F from the graph the length of the shortest path between s and t in the resulting graph has at least L edges.

We show that the minimal length-bounded L-cut can be computed in linear time with respect to L and the tree-width of the input graph as parameters.

It is possible to derive an FPT algorithm for the minimal length-bounded L-cut when parametrized by the tree-depth only.

On the other hand the minimal length-bounded L-cut problem is W[1]-hard when parametrized by path-width.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010