From few components to an Eulerian graph by adding arcs

Manuel Sorge, René Van Bevern, Rolf Niedermeier, Mathias Weller

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

15 Цитирования (Scopus)

Аннотация

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

Язык оригиналаанглийский
Название основной публикацииGraph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Revised Papers
Страницы307-318
Число страниц12
DOI
СостояниеОпубликовано - 1 дек 2011
Опубликовано для внешнего пользованияДа
Событие37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011 - Tepla Monastery, Чехия
Продолжительность: 21 июн 201124 июн 2011

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том6986 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция37th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2011
СтранаЧехия
ГородTepla Monastery
Период21.06.201124.06.2011

Fingerprint Подробные сведения о темах исследования «From few components to an Eulerian graph by adding arcs». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать