direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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.

Zusatzinformationen / Extras