Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
From Few Components to an Eulerian Graph by Adding Arcs
verfasst von : Manuel Sorge, René van Bevern, Rolf Niedermeier, Mathias Weller
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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”.