TU Berlin

Talk 08.06.2011

isti-logo

Page Content

to Navigation

From Few Components to an Eulerian Graph by Adding Arcs

Manuel Sorge (TU Berlin)
Eulerian Extension (EE) is the problem to make an arc-weighted directed multigraph Eulerian by adding arcs at minimum cost. EE is NP-hard and has been shown fixed-parameter tractable with respect to the number of arc additions.  Complementing this result, on the way to answering a long-standing open question, we show that EE is fixed-parameter tractable with respect to the combined parameter "number of connected components in the underlying undirected multigraph"and "sum of indeg(v) - outdeg(v) over all vertices v in the input multigraph where this value is positive".  Moreover, we show that EE has no polynomial-size problem kernel with respect to this parameter combination and for the parameter "number of arc additions".

date
speaker
location
language
08.06.2011 14:15
Manuel Sorge
FR 6510
english


Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe