The complexity of gerrymandering over graphs: paths and trees

DOI10.1016/j.dam.2022.09.009zbMath1502.91049OpenAlexW3129684758MaRDI QIDQ5918559

Tomohiro Koana, Rolf Niedermeier, Matthias Bentert

Publication date: 11 November 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2022.09.009

zbMATH Keywords

graph algorithmsNP-hardnessmultiparty electionsbounded-diameter graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) History, political science (91F10)

Cites Work

• Unnamed Item
• Editing graphs to satisfy degree constraints: a parameterized approach
• On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering
• Algorithms for gerrymandering over graphs
• Bicolored graph partitioning, or: gerrymandering at its worst
• Gerrymandering on graphs: computational complexity and parameterized algorithms