## Manuel Sorge, René van Bevern, Rolf Niedermeier, and Mathias Weller.
From few components to an eulerian graph by adding arcs.
In *Proceedings of the 37th International Workshop on
Graph-Theoretic Concepts in Computer Science (WG'11), Teplá Monastery, Czech
Republic*, volume 6986 of *Lecture Notes in Computer Science*, pages
307–318. Springer, 2011.

Eulerian Extension (EE) is the problem to make an
arc-weighted directed multigraph Eulerian by adding
arcs of minimum total 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 an 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 is unlikely to admit a polynomial-size
problem kernel for this parameter combination and for
the parameter “number of arc additions”.

[ bib |
DOI |
.pdf ]
Back

*This file was generated by
bibtex2html 1.98.*