Network-based dissolution

R. Bevern, van, R. Bredereck, J. Chen, V. Froese, R. Niedermeier, G.J. Woeginger

Onderzoeksoutput: Boek/rapportRapportAcademic

86 Downloads (Pure)


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.
Originele taal-2Engels
Aantal pagina's29
StatusGepubliceerd - 2014

Publicatie series

Volume1402.2664 [cs.DM]

Vingerafdruk Duik in de onderzoeksthema's van 'Network-based dissolution'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Bevern, van, R., Bredereck, R., Chen, J., Froese, V., Niedermeier, R., & Woeginger, G. J. (2014). Network-based dissolution. (arXiv; Vol. 1402.2664 [cs.DM]). s.n.