Schidler, A. (2022). SAT-Based Local Search for Plane Subgraph Partitions. In X. Goaoc & M. Kerber (Eds.), 38th International Symposium on Computational Geometry (SoCG 2022) (pp. 1–8). Schloss Dagstuhl --Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2022.74
38th International Symposium on Computational Geometry (SoCG 2022)
-
Event date:
7-Jun-2022 - 10-Jun-2022
-
Event place:
Berlin, Germany
-
Number of Pages:
8
-
Publisher:
Schloss Dagstuhl --Leibniz-Zentrum für Informatik, Dagstuhl
-
Keywords:
graph coloring; large neighborhood search; local improvement; logic; plane subgraphs; SAT; SLIM
en
Abstract:
The Partition into Plane Subgraphs Problem (PPS) asks to partition the edges of a geometric graph with straight line segments into as few classes as possible, such that the line segments within a class do not cross. We discuss our approach GC-SLIM: a local search method that views PPS as a graph coloring problem and tackles it with a new and unique combination of propositional satisfiability (SAT) and tabu search, achieving the fourth place in the 2022 CG:SHOP Challenge.
en
Project title:
SAT-Basierende lokale Verbesserungsmethoden: P32441-N35 (FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)) Revealing and Utilizing the Hidden Structure for Solving Hard Problems in AI: ICT19-065 (WWTF Wiener Wissenschafts-, Forschu und Technologiefonds)
CC BY 4.0
