TU Berlin

Talk 08.06.2011

isti-logo

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

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

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe