TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 06.11.2014

isti-logo

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Network-Based Dissolution

Dr. Robert Bredereck (TU Berlin)

We introduce a novel graph-theoretic dissolution model which applies to a number of redistribution scenarios such as gerrymandering or work economization. The central aspect of our model is to delete some vertices and redistribute their "load" to neighboring vertices in a completely balanced way. We investigate how the underlying graph structure, the pre-knowledge about which vertices to delete, and the relation between old and new "vertex load" influence the computational complexity of the underlying easy-to-describe graph problems, thereby identifying both tractable and intractable cases.

Date
Speaker
Location
Language
06.11.2014
16:15
Robert Bredereck
TEL 512
english

Back to the research colloquium site.

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe