Document Open Access Logo

Shadoks Approach to Minimum Partition into Plane Subgraphs (CG Challenge)

Authors Loïc Crombez , Guilherme D. da Fonseca , Yan Gerard , Aldo Gonzalez-Lorenzo

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.71.pdf
  • Filesize: 0.65 MB
  • 8 pages

Document Identifiers

Author Details

Loïc Crombez
  • LIMOS, Université Clermont Auvergne, Aubière, France
Guilherme D. da Fonseca
  • LIS, Aix-Marseille Université, France
Yan Gerard
  • LIMOS, Université Clermont Auvergne, Aubière, France
Aldo Gonzalez-Lorenzo
  • LIS, Aix-Marseille Université, France

Funding

  • da Fonseca, Guilherme D.: This work is supported by the French ANR PRC grant ADDS (ANR-19-CE48-0005).
  • Gerard, Yan: This work is supported by the French ANR PRC grant ADDS (ANR-19-CE48-0005).
  • Gonzalez-Lorenzo, Aldo: This work is supported by the French ANR PRC grant COHERENCE4D (ANR-20-CE10-0002).

Acknowledgements

We would like to thank Hélène Toussaint, Raphaël Amato, Boris Lonjon, and William Guyot-Lénat from LIMOS, as well as the Qarma and TALEP teams and Manuel Bertrand from LIS, who continue to make the computational resources of the LIMOS and LIS clusters available to our research. We would also like to thank the challenge organizers and other competitors for their time, feedback, and making this whole event possible.

Cite AsGet BibTex

Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, and Aldo Gonzalez-Lorenzo. Shadoks Approach to 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. 71:1-71:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.71

Abstract

We explain the heuristics used by the Shadoks team to win first place in the CG:SHOP 2022 challenge that considers the minimum partition into plane subgraphs. The goal is to partition a set of segments into as few subsets as possible such that segments in the same subset do not cross each other. The challenge has given 225 instances containing between 2500 and 75000 segments. For every instance, our solution was the best among all 32 participating teams.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Plane graphs
  • graph coloring
  • intersection graph
  • conflict optimizer
  • line segments
  • computational geometry

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. 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, pages 63:1-63:9, 2021. Google Scholar
  3. David Eppstein. Small maximal independent sets and faster exact graph coloring. J. Graph Algorithms Appl, 7(2):131-140, 2002. Google Scholar
  4. 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.
  5. 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:7, 2022. Google Scholar
  6. Philippe Galinier and Jin-Kao Hao. Hybrid evolutionary algorithms for graph coloring. Journal of combinatorial optimization, 3(4):379-397, 1999. Google Scholar
  7. Stefano Gualandi and Federico Malucelli. Exact solution of graph coloring problems via constraint programming and column generation. INFORMS Journal on Computing, 24(1):81-100, 2012. Google Scholar
  8. Alain Hertz and Dominique de Werra. Using tabu search techniques for graph coloring. Computing, 39(4):345-351, 1987. Google Scholar
  9. Tommy R. Jensen and Bjarne Toft. Graph coloring problems. John Wiley & Sons, 2011. Google Scholar
  10. David E. Joslin and David P. Clements. Squeaky wheel optimization. Journal of Artificial Intelligence Research, 10:353-373, 1999. Google Scholar
  11. R. M. R. Lewis. A Guide to Graph Colouring: Algorithms and Applications. Springer Publishing Company, Incorporated, 1st edition, 2015. Google Scholar
  12. Corinne Lucet, Florence Mendes, and Aziz Moukrim. An exact method for graph coloring. Computers & Operations Research, 33(8):2189-2207, 2006. Google Scholar
  13. David W. Matula, George Marble, and Joel D. Isaacson. Graph coloring algorithms. In Graph theory and computing, pages 109-122. Elsevier, 1972. Google Scholar
  14. Isabel Méndez-Díaz and Paula Zabala. A branch-and-cut algorithm for graph coloring. Discrete Applied Mathematics, 154(5):826-847, 2006. Google Scholar
  15. André Schidler. SAT-based local search for plane subgraph partitions. In Symposium on Computational Geometry (SoCG), pages 74:1-74:8, 2022. Google Scholar
  16. Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng. Conflict-based local search for minimum partition into plane subgraphs. In Symposium on Computational Geometry (SoCG), pages 72:1-72:6, 2022. 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