Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Network-based vertex dissolution. / Van Bevern, René; Bredereck, Robert; Chen, Jiehua и др.
в: SIAM Journal on Discrete Mathematics, Том 29, № 2, 01.01.2015, стр. 888-914.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
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