TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 06.11.2014

isti-logo

Page Content

to Navigation

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

Quick Access

Schnellnavigation zur Seite über Nummerneingabe