RenĂ© van Bevern, Robert Bredereck, Jiehua Chen, Vincent Froese, Rolf Niedermeier, and Gerhard J. Woeginger. Network-based dissolution. In Proceedings of 39th International Symposium on Mathematical Foundations of Computer Science (MFCS'14), Budapest, Hungary, volume 8635 of Lecture Notes in Computer Science, pages 69–80. Springer, 2014. The final version of this article appeared in SIAM Journal on Discrete Mathematics.

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.

bib | DOI | journal version ] Back

This file was generated by bibtex2html 1.98.