Finding Shortest Flip Sequences Between Connected Graph Partitions

References

• Akitaya HA, Korman M, Korten O, Souvaine DL, Tóth CD (2022) Reconfiguration of connected graph partitions via recombination. Theoret. Comput. Sci. 923(1):13–26.Google Scholar
• Akitaya HA, Jones MD, Korman M, Korten O, Meierfrankenfeld C, Munje MJ, Souvaine DL, Thramann M, Tóth CD (2023) Reconfiguration of connected graph partitions. J. Graph Theory 102(1):35–66.Google Scholar
• Almudevar A, Field C (1999) Estimation of single-generation sibling relationships based on DNA markers. J. Agricultural Biol. Environ. Statist. 4(2):136–165.Google Scholar
• Arredondo V, Martínez-Panero M, Peña T, Ricca F (2021) Mathematical political districting taking care of minority groups. Ann. Oper. Res. 305(1–2):375–402.Google Scholar
• Autry EA, Carter D, Herschlag GJ, Hunter Z, Mattingly JC (2021) Metropolized multiscale forest recombination for redistricting. Multiscale Modeling Simulation 19(4):1885–1914.Google Scholar
• Bichot CE, Siarry P (2011) Graph Partitioning (ISTE Ltd. and John Wiley & Sons, Inc., Hoboken, NJ).Google Scholar
• Borgwardt S, Happach F, Zirkelbach S (2023) An algorithm for the separation-preserving transition of clusterings. INFORMS J. Optim. 5(1):1–26.Link, Google Scholar
• Bose P, Dujmović V, Hurtado F, Morin P (2009) Connectivity-preserving transformations of binary images. Comput. Vision Image Understanding 113(10):1027–1038.Google Scholar
• Bozkaya B, Erkut E, Laporte G (2003) A tabu search heuristic and adaptive memory procedure for political districting. Eur. J. Oper. Res. 144(1):12–26.Google Scholar
• Cardoso JS, Corte-Real L (2005) Toward a generic evaluation of image segmentation. IEEE Trans. Image Processing 14(11):1773–1782.Google Scholar
• Chikina M, Frieze A, Pegden W (2017) Assessing significance in a Markov chain without mixing. Proc. Natl. Acad. Sci. USA 114(11):2860–2864.Google Scholar
• Cho WKT, Liu YY (2018) Sampling from complicated and unknown distributions: Monte Carlo and Markov Chain Monte Carlo methods for redistricting. Physica A: Statist. Mech. Appl. 506:170–178.Google Scholar
• Cho WKT, Liu YY (2021) A parallel evolutionary multiple-try Metropolis Markov chain Monte Carlo algorithm for sampling spatial partitions. Statist. Comput. 31(10):2860–2864.Google Scholar
• Day WH (1981) The complexity of computing metric distance between partitions. Math. Soc. Sci. 14(11):269–287.Google Scholar
• Dechter R, Pearl J (1985) Generalized best-first search strategies and the optimality of A*. J. Assoc. Comput. Machinery 32(3):505–536.Google Scholar
• DeFord D, Duchin M, Solomon J (2021) Recombination: A family of Markov chains for redistricting. Harv. Data Sci. Rev. 3(1).Google Scholar
• Dijkstra E (1959) A note on two problems in connexion with graphs. Numer. Math. 1(1):269–271.Google Scholar
• Dobbs KW (2024) Optimization methods for political redistricting. PhD dissertation, University of Illinois Urbana-Champaign, Champaign, IL.Google Scholar
• Dobbs KW, King DM, Jacobson SH (2023) Redistricting optimization with recombination: A local search case study. Comput. Oper. Res. 160(1):1–19.Google Scholar
• Dobbs KW, King DM, Ludden IG, Jacobson SH (2024a) Facilitating compromise in redistricting with transfer distance midpoints. INFORMS J. Optim. 6(3–4):214–239.Link, Google Scholar
• Dobbs KW, Swamy R, King DM, Ludden IG, Jacobson SH (2024b) An optimization case study in analyzing Missouri redistricting. INFORMS J. Appl. Analytics 54(2):162–187.Link, Google Scholar
• Dumitrescu A, Pach J (2006) Pushing squares around. Graphs Comb. 22(1):37–50.Google Scholar
• Dyer M, Frieze A (1985) On the complexity of partitioning graphs into connected subgraphs. Discrete Appl. Math. (1979) 10(2):139–153.Google Scholar
• Fifield B, Higgins M, Imai K, Tarr A (2020) Automated redistricting simulation using Markov Chain Monte Carlo. J. Comput. Graph. Statist. 29(4):715–728.Google Scholar
• Gusfield D (2002) Partition-distance: A problem and class of perfect graphs arising in clustering. Inform. Processing Lett. 82(3):159–164.Google Scholar
• Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Systems Sci. Cybernetics 4(2):100–107.Google Scholar
• Herschlag G, Kang H, Luo J, Graves CV, Bangia S, Ravier R, Mattingly J (2020) Quantifying gerrymandering in North Carolina. Statist. Public Policy 7(1):30–38.Google Scholar
• Hess S, Weaver J, Siegfeldt H, Whelan J, Zitlau P (1965) Nonpartisan political redistricting by computer. Oper. Res. 13(6):998–1006.Link, Google Scholar
• King DM, Jacobson SH, Sewell EC, Cho WKT (2012) Geo-graphs: An efficient model for enforcing contiguity and hole constraints in planar graph partitioning. Oper. Res. 60(5):1213–1228.Link, Google Scholar
• Komuravelli A, Sinha A, Bishnu A (2009) Connectivity preserving transformations for higher dimensional binary images. Discrete Appl. Math. (1979) 157(16):3372–3385.Google Scholar
• Konovalov DA, Litow B, Bajema N (2005) Partition-distance via the assignment problem. Bioinformatics 21(10):2463–2468.Google Scholar
• Ludden IG, Swamy R, King DM, Jacobson SH (2023) A bisection protocol for political redistricting. INFORMS J. Optim. 5(3):233–255.Link, Google Scholar
• Metric Geometry and Gerrymandering Group (2018a) GerryChain. Accessed October 19, 2023, https://github.com/mggg/GerryChain.Google Scholar
• Metric Geometry and Gerrymandering Group (2018b) The known sizes of grid metagraphs. Accessed June 23, 2025, https://mggg.org/table.Google Scholar
• Morrison DR, Jacobson SH, Sauppe JJ, Sewell EC (2016) Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optim. 19(1):79–102.Google Scholar
• National Conference of State Legislatures (2024a) Redistricting and census. Accessed March 27, 2024, https://www.ncsl.org/redistricting-and-census.Google Scholar
• National Conference of State Legislatures (2024b) Redistricting criteria. Accessed July 31, 2024, https://www.ncsl.org/research/redistricting/redistricting-criteria.aspx.Google Scholar
• Pegden W, Procaccia AD, Yu D (2017) A partisan districting protocol with provably nonpartisan outcomes. Preprint, submitted October 24, https://arxiv.org/abs/1710.08781.Google Scholar
• Peng B, Zhang L, Zhang D (2013) A survey of graph theoretical approaches to image segmentation. Pattern Recognition 46(3):1020–1038.Google Scholar
• Pinto da Costa JF, Rao P (2004) Central partition for a partition-distance and strong pattern graph. REVSTAT Statist. J. 2(2):127–143.Google Scholar
• Reynolds v Sims (1964) 377 U.S. 533. Accessed July 31, 2023, https://supreme.justia.com/cases/federal/us/377/533/.Google Scholar
• Ricca F, Scozzari A (2020) Mathematical programming formulations for practical political districting. Ríos-Mercado RZ, ed. Optimal Districting and Territory Design, chapter 6 (Springer, Cham, Switzerland), 105–128.Google Scholar
• Ricca F, Simeone B (2008) Local search algorithms for political districting. Eur. J. Oper. Res. 189(3):1409–1426.Google Scholar
• Ricca F, Scozzari A, Simeone B (2013) Political districting: From classical models to recent approaches. Ann. Oper. Res. 204(1):271–299.Google Scholar
• Swamy R, King DM, Jacobson SH (2022) Multi-objective optimization for politically fair districting: A scalable multilevel approach. Oper. Res. 71(2):536–562.Google Scholar
• Swamy R, King DM, Ludden IG, Dobbs KW, Jacobson SH (2024) A practical optimization framework for political redistricting: A case study in Arizona. Socioeconom. Planning Sci. 92(1):1–18.Google Scholar
• Validi H, Buchanan A (2022) Political districting to minimize cut edges. Math. Programming Comput. 14(4):623–672.Google Scholar
• Validi H, Buchanan A, Lykhovyd E (2021) Imposing contiguity constraints in political districting models. Oper. Res. 70(2):867–892.Link, Google Scholar
• Wesberry v Sanders (1964) 376 U.S. 1. Accessed July 31, 2023, https://supreme.justia.com/cases/federal/us/376/1/.Google Scholar
• Wolsey L (2021) Integer Programming (John Wiley & Sons, Inc., Hoboken, NJ).Google Scholar
• Zhang H, Lin L, Xu L, Wang X (2021) Graph partition based privacy-preserving scheme in social networks. J. Network Comput. Appl. 195(1):1–12.Google Scholar