direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

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".

08.06.2011 14:15
Manuel Sorge
FR 6510

Back to the research colloquium site.