## RenĂ© van Bevern, Robert Bredereck, Jiehua Chen, Vincent Froese, Rolf
Niedermeier, and Gerhard J. Woeginger.
Network-based vertex dissolution.
*SIAM Journal on Discrete Mathematics*, 29(2):888–914, 2015.

We introduce a graph-theoretic vertex 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 load to neighboring vertices in a completely
balanced way. We investigate how the underlying graph
structure, the 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.

[ bib |
DOI |
http ]
Back

*This file was generated by
bibtex2html 1.98.*