Algorithms for gerrymandering over graphs

DOI10.1016/J.TCS.2021.03.037MaRDI QIDQ831130zbMATH OpenOpenAlexFDO

Authors Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Publication date 10 May 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2021.03.037

zbMATH Keywords

gerrymanderinggraph algorithmscomputational social choice

Mathematics Subject Classification ID

Social choice (91B14) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic game theory and complexity (91A68)

Recommendations

• The complexity of gerrymandering over graphs: paths and trees
• Gerrymandering on graphs: computational complexity and parameterized algorithms
• Priced gerrymandering
• Optimal partisan districting on planar geographies
• On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A tabu search heuristic and adaptive memory procedure for political districting
• An optimization based heuristic for political districting
• Anyone but him: the complexity of precluding an alternative
• Bicolored graph partitioning, or: gerrymandering at its worst
• Control and bribery in voting
• Control complexity in Bucklin and fallback voting: a theoretical analysis
• How hard is it to control an election?
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• More natural models of electoral control by partition
• Network-based vertex dissolution
• On the complexity of partitioning graphs into connected subgraphs
• Optimal partisan districting on planar geographies
• Optimal redistricting under geographical constraints: why ``pack and crack does not work
• Parameterized complexity of candidate control in elections and related digraph problems
• Parameterized computational complexity of control problems in voting systems
• The computational difficulty of manipulating an election

Cited in

(17)

• Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions
• Gerrymandering on graphs: computational complexity and parameterized algorithms
• Redistricting algorithms
• A discrete districting plan
• Optimal partisan districting on planar geographies
• Bicolored graph partitioning, or: gerrymandering at its worst
• Priced gerrymandering
• Parameterized complexity of gerrymandering
• On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering
• A fast sorting algorithm to redistricting election model
• Optimal redistricting under geographical constraints: why ``pack and crack does not work
• Gerrymandering and Convexity
• Reconfiguration of connected graph partitions
• Network-based dissolution
• Network-based vertex dissolution
• The complexity of gerrymandering over graphs: paths and trees
• The complexity of gerrymandering over graphs: paths and trees

This page was built for publication: Algorithms for gerrymandering over graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q831130)