Document Open Access Logo

Conflict-Based Local Search for Minimum Partition into Plane Subgraphs (CG Challenge)

Authors Jack Spalding-Jamieson , Brandon Zhang , Da Wei Zheng

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.72.pdf
  • Filesize: 0.53 MB
  • 6 pages

Document Identifiers

Author Details

Jack Spalding-Jamieson
  • David R. Cheriton School of Computer Science, University of Waterloo, Canada
Brandon Zhang
  • Vancouver, Canada
Da Wei Zheng
  • Department of Computer Science, University of Illinois at Urbana-Champaign, IL, USA

Cite AsGet BibTex

Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng. Conflict-Based Local Search for Minimum Partition into Plane Subgraphs (CG Challenge). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 72:1-72:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.72

Abstract

This paper examines the approach taken by team gitastrophe in the CG:SHOP 2022 challenge. The challenge was to partition the edges of a geometric graph, with vertices represented by points in the plane and edges as straight lines, into the minimum number of planar subgraphs. We used a simple variation of a conflict optimizer strategy used by team Shadoks in the previous year’s CG:SHOP to rank second in the challenge.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Design and analysis of algorithms
Keywords
  • local search
  • planar graph
  • graph colouring
  • geometric graph
  • conflict optimizer

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Daniel Brélaz. New methods to color the vertices of a graph. Communications of the ACM, 22(4):251-256, 1979. Google Scholar
  2. Jeff Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. Problems in analysis, 625(195-199):110, 1970. Google Scholar
  3. Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, and Aldo Gonzalez-Lorenzo. Shadoks approach to minimum partition into plane subgraphs. In Symposium on Computational Geometry (SoCG), pages 71:1-71:8, 2022. Google Scholar
  4. Loïc Crombez, Guilherme D da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, and Luc Libralesso. Shadoks approach to low-makespan coordinated motion planning (cg challenge). In 37th International Symposium on Computational Geometry (SoCG 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  5. Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, and Stefan Schirra. Minimum partition into plane subgraphs: The CG: SHOP Challenge 2022. CoRR, abs/2203.07444, 2022. URL: http://arxiv.org/abs/2203.07444.
  6. Florian Fontan, Pascal Lafourcade, Luc Libralesso, and Benjamin Momège. Local search with weighting schemes for the CG:SHOP 2022 competition. In Symposium on Computational Geometry (SoCG), pages 73:1-73:6, 2022. Google Scholar
  7. Olivier Goudet, Cyril Grelier, and Jin-Kao Hao. A deep learning guided memetic framework for graph coloring problems, 2021. URL: http://arxiv.org/abs/2109.05948.
  8. Alain Hertz and Dominique de Werra. Using tabu search techniques for graph coloring. Computing, 39(4):345-351, 1987. Google Scholar
  9. David S Johnson and Michael A Trick. Cliques, coloring, and satisfiability: second DIMACS implementation challenge, October 11-13, 1993, volume 26. American Mathematical Soc., 1996. Google Scholar
  10. Laurent Moalic and Alexandre Gondran. Variations on memetic algorithms for graph coloring problems. Journal of Heuristics, 24(1):1-24, 2018. Google Scholar
  11. Daniel Cosmin Porumbel, Jin-Kao Hao, and Pascale Kuntz. An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring. Computers & Operations Research, 37(10):1822-1832, 2010. Google Scholar
  12. André Schidler. SAT-based local search for plane subgraph partitions. In Symposium on Computational Geometry (SoCG), pages 74:1-74:8, 2022. Google Scholar
  13. Olawale Titiloye and Alan Crispin. Quantum annealing of the graph coloring problem. Discret. Optim., 8:376-384, 2011. Google Scholar
  14. Olawale Titiloye and Alan Crispin. Parameter tuning patterns for random graph coloring with quantum annealing. PloS one, 7(11):e50060, 2012. Google Scholar
  15. D. J. A. Welsh and M. B. Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1):85-86, January 1967. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact