Standard

From few components to an Eulerian graph by adding arcs. / Sorge, Manuel; Van Bevern, René; Niedermeier, Rolf и др.

Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers. 2011. стр. 307-318 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 6986 LNCS).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование

Harvard

Sorge, M, Van Bevern, R, Niedermeier, R & Weller, M 2011, From few components to an Eulerian graph by adding arcs. в 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), Том. 6986 LNCS, стр. 307-318, 37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011, Tepla Monastery, Чехия, 21.06.2011. https://doi.org/10.1007/978-3-642-25870-1_28

APA

Sorge, M., Van Bevern, R., Niedermeier, R., & Weller, M. (2011). From few components to an Eulerian graph by adding arcs. в Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers (стр. 307-318). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 6986 LNCS). https://doi.org/10.1007/978-3-642-25870-1_28

Vancouver

Sorge M, Van Bevern R, Niedermeier R, Weller M. From few components to an Eulerian graph by adding arcs. в Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers. 2011. стр. 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 и др. / From few components to an Eulerian graph by adding arcs. Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers. 2011. стр. 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 -

ID: 22341856