Network-based dissolution

René Van Bevern, Robert Bredereck, Jiehua Chen, Vincent Froese, Rolf Niedermeier, Gerhard J. Woeginger

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

Аннотация

We introduce a graph-theoretic dissolution model that applies to a number of redistribution scenarios such as gerrymandering in political districting or work balancing in an online situation. The central aspect of our model is the deletion of certain vertices and the redistribution of their loads to neighboring vertices in a perfectly balanced way. We investigate how the underlying graph structure, the pre-knowledge of which vertices should be deleted, and the relation between old and new vertex loads influence the computational complexity of the underlying graph problems. Our results establish a clear borderline between tractable and intractable cases.

Язык оригиналаанглийский
Название основной публикацииMathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Proceedings
ИздательSpringer-Verlag GmbH and Co. KG
Страницы69-80
Число страниц12
ИзданиеPART 2
ISBN (печатное издание)9783662444641
DOI
СостояниеОпубликовано - 1 янв 2014
Опубликовано для внешнего пользованияДа
Событие39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014 - Budapest, Венгрия
Продолжительность: 25 авг 201429 авг 2014

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

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

Конференция

Конференция39th International Symposium on Mathematical Foundations of Computer Science, MFCS 2014
СтранаВенгрия
ГородBudapest
Период25.08.201429.08.2014

Fingerprint Подробные сведения о темах исследования «Network-based dissolution». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Van Bevern, R., Bredereck, R., Chen, J., Froese, V., Niedermeier, R., & Woeginger, G. J. (2014). Network-based dissolution. В Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Proceedings (PART 2 ред., стр. 69-80). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 8635 LNCS, № PART 2). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-662-44465-8_7