Standard
From few components to an Eulerian graph by adding arcs. / Sorge, Manuel; Van Bevern, René; Niedermeier, Rolf et al.
Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers. 2011. p. 307-318 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6986 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Sorge, M
, Van Bevern, R, Niedermeier, R & Weller, M 2011,
From few components to an Eulerian graph by adding arcs. in
Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6986 LNCS, pp. 307-318, 37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011, Tepla Monastery, Czech Republic,
21.06.2011.
https://doi.org/10.1007/978-3-642-25870-1_28APA
Vancouver
Sorge M
, Van Bevern R, Niedermeier R, Weller M.
From few components to an Eulerian graph by adding arcs. In Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers. 2011. p. 307-318. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-25870-1_28
Author
Sorge, Manuel
; Van Bevern, René ; Niedermeier, Rolf et al. /
From few components to an Eulerian graph by adding arcs. Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers. 2011. pp. 307-318 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{b4ab4838644344cf953a43b04362070d,
title = "From few components to an Eulerian graph by adding arcs",
abstract = "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{"}.",
author = "Manuel Sorge and {Van Bevern}, Ren{\'e} and Rolf Niedermeier and Mathias Weller",
year = "2011",
month = dec,
day = "1",
doi = "10.1007/978-3-642-25870-1_28",
language = "English",
isbn = "9783642258695",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "307--318",
booktitle = "Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers",
note = "37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011 ; Conference date: 21-06-2011 Through 24-06-2011",
}
RIS
TY - GEN
T1 - From few components to an Eulerian graph by adding arcs
AU - Sorge, Manuel
AU - Van Bevern, René
AU - Niedermeier, Rolf
AU - Weller, Mathias
PY - 2011/12/1
Y1 - 2011/12/1
N2 - 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".
AB - 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".
UR - http://www.scopus.com/inward/record.url?scp=84855394417&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-25870-1_28
DO - 10.1007/978-3-642-25870-1_28
M3 - Conference contribution
AN - SCOPUS:84855394417
SN - 9783642258695
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 307
EP - 318
BT - Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers
T2 - 37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011
Y2 - 21 June 2011 through 24 June 2011
ER -
