Network-based dissolution

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

doi:10.1007/978-3-662-44465-8_7

Network-based dissolution

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

Discrete Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

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.

Original language	English
Title of host publication	Mathematical Foundations of Computer Science 2014 (39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II)
Editors	E. Csuhaj-Varjú, M. Dietzfelbinger, Z. Ésik
Place of Publication	Berlin
Publisher	Springer
Pages	69-80
ISBN (Print)	978-3-662-44464-1
DOIs	https://doi.org/10.1007/978-3-662-44465-8_7
Publication status	Published - 2014
Event	39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014) - Budapest, Hungary Duration: 25 Aug 2014 → 29 Aug 2014 Conference number: 39

Publication series

Name	Lecture Notes in Computer Science
Volume	8635
ISSN (Print)	0302-9743

Conference

Conference	39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014)
Abbreviated title	MFCS 2014
Country/Territory	Hungary
City	Budapest
Period	25/08/14 → 29/08/14

Access to Document

10.1007/978-3-662-44465-8_7

Cite this

Bevern, van, R., Bredereck, R., Chen, J., Froese, V., Niedermeier, R., & Woeginger, G. J. (2014). Network-based dissolution. In E. Csuhaj-Varjú, M. Dietzfelbinger, & Z. Ésik (Eds.), Mathematical Foundations of Computer Science 2014 (39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II) (pp. 69-80). (Lecture Notes in Computer Science; Vol. 8635). Springer. https://doi.org/10.1007/978-3-662-44465-8_7

@inproceedings{6cc3afd2ef494727803555767eefefb8,

title = "Network-based dissolution",

abstract = "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.",

author = "\{Bevern, van\}, R. and R. Bredereck and J. Chen and V. Froese and R. Niedermeier and G.J. Woeginger",

year = "2014",

doi = "10.1007/978-3-662-44465-8\_7",

language = "English",

isbn = "978-3-662-44464-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "69--80",

editor = "E. Csuhaj-Varj{\'u} and M. Dietzfelbinger and Z. {\'E}sik",

booktitle = "Mathematical Foundations of Computer Science 2014 (39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II)",

address = "Germany",

note = "39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014), MFCS 2014 ; Conference date: 25-08-2014 Through 29-08-2014",

}

Bevern, van, R, Bredereck, R, Chen, J, Froese, V, Niedermeier, R & Woeginger, GJ 2014, Network-based dissolution. in E Csuhaj-Varjú, M Dietzfelbinger & Z Ésik (eds), Mathematical Foundations of Computer Science 2014 (39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II). Lecture Notes in Computer Science, vol. 8635, Springer, Berlin, pp. 69-80, 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014), Budapest, Hungary, 25/08/14. https://doi.org/10.1007/978-3-662-44465-8_7

Network-based dissolution. / Bevern, van, R.; Bredereck, R.; Chen, J. et al.
Mathematical Foundations of Computer Science 2014 (39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II). ed. / E. Csuhaj-Varjú; M. Dietzfelbinger; Z. Ésik. Berlin: Springer, 2014. p. 69-80 (Lecture Notes in Computer Science; Vol. 8635).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Network-based dissolution

AU - Bevern, van, R.

AU - Bredereck, R.

AU - Chen, J.

AU - Froese, V.

AU - Niedermeier, R.

AU - Woeginger, G.J.

N1 - Conference code: 39

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-662-44465-8_7

DO - 10.1007/978-3-662-44465-8_7

M3 - Conference contribution

SN - 978-3-662-44464-1

T3 - Lecture Notes in Computer Science

SP - 69

EP - 80

BT - Mathematical Foundations of Computer Science 2014 (39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II)

A2 - Csuhaj-Varjú, E.

A2 - Dietzfelbinger, M.

A2 - Ésik, Z.

PB - Springer

CY - Berlin

T2 - 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014)

Y2 - 25 August 2014 through 29 August 2014

ER -

Bevern, van R, Bredereck R, Chen J, Froese V, Niedermeier R, Woeginger GJ. Network-based dissolution. In Csuhaj-Varjú E, Dietzfelbinger M, Ésik Z, editors, Mathematical Foundations of Computer Science 2014 (39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II). Berlin: Springer. 2014. p. 69-80. (Lecture Notes in Computer Science). doi: 10.1007/978-3-662-44465-8_7

Network-based dissolution

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this