Standard

Network-based vertex dissolution. / Van Bevern, René; Bredereck, Robert; Chen, Jiehua et al.

In: SIAM Journal on Discrete Mathematics, Vol. 29, No. 2, 01.01.2015, p. 888-914.

Research output: Contribution to journal › Article › peer-review

Harvard

Van Bevern, R, Bredereck, R, Chen, J, Froese, V, Niedermeier, R & Woeginger, GJ 2015, 'Network-based vertex dissolution', SIAM Journal on Discrete Mathematics, vol. 29, no. 2, pp. 888-914. https://doi.org/10.1137/140978880

APA

Van Bevern, R., Bredereck, R., Chen, J., Froese, V., Niedermeier, R., & Woeginger, G. J. (2015). Network-based vertex dissolution. SIAM Journal on Discrete Mathematics, 29(2), 888-914. https://doi.org/10.1137/140978880

Vancouver

Van Bevern R, Bredereck R, Chen J, Froese V, Niedermeier R, Woeginger GJ. Network-based vertex dissolution. SIAM Journal on Discrete Mathematics. 2015 Jan 1;29(2):888-914. doi: 10.1137/140978880

Author

Van Bevern, René ; Bredereck, Robert ; Chen, Jiehua et al. / Network-based vertex dissolution. In: SIAM Journal on Discrete Mathematics. 2015 ; Vol. 29, No. 2. pp. 888-914.

BibTeX

@article{3095ac613cf0412b83e0b282b88a0d93,
title = "Network-based vertex dissolution",
abstract = "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.",
keywords = "Combinatorial algorithms, Computational complexity analysis, Economization, Election control, Flow networks, Matching, NP-hard problems, Political districting, Redistribution scenarios",
author = "{Van Bevern}, Ren{\'e} and Robert Bredereck and Jiehua Chen and Vincent Froese and Rolf Niedermeier and Woeginger, {Gerhard J.}",
year = "2015",
month = jan,
day = "1",
doi = "10.1137/140978880",
language = "English",
volume = "29",
pages = "888--914",
journal = "SIAM Journal on Discrete Mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "2",

}

RIS

TY - JOUR

T1 - Network-based vertex dissolution

AU - Van Bevern, René

AU - Bredereck, Robert

AU - Chen, Jiehua

AU - Froese, Vincent

AU - Niedermeier, Rolf

AU - Woeginger, Gerhard J.

PY - 2015/1/1

Y1 - 2015/1/1

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

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

KW - Combinatorial algorithms

KW - Computational complexity analysis

KW - Economization

KW - Election control

KW - Flow networks

KW - Matching

KW - NP-hard problems

KW - Political districting

KW - Redistribution scenarios

UR - http://www.scopus.com/inward/record.url?scp=84938077718&partnerID=8YFLogxK

U2 - 10.1137/140978880

DO - 10.1137/140978880

M3 - Article

AN - SCOPUS:84938077718

VL - 29

SP - 888

EP - 914

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 2

ER -

ID: 22342382