What's on in Computing Science?
Date: Wednesday, 7 December, 2005
F121 conference room
Roman Domination - a case study on parameterized complexity
Dr Henning Fernau, University of Trier
We are going to present some of the main ideas of parameterized
complexity by studying the classical problem of Roman domination,
a graph theoretic problem that can be traced back to the Roman
This way, we introduce the main classes of this branch of complexity
theory, as well as introducing the main methods in use for the
development of parameterized algorithms. This also exhibits that
this theory may present a method for getting efficient algorithms
when fixing the parameter.
More precisely (and more technically), we show that the Roman
domination problem is W-hard on general graphs but is
parameterized tractable on planar graphs.
Moreover, a certain version of parameterized dual of Roman domination
is fixed-parameter tractable.
Contact: Dr David F Manlove (firstname.lastname@example.org)
URL: Roman Domination - a case study on parameterized complexity
Add to my calendar