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)
-
Veranstaltungszeitraum:
7-Jun-2022 - 10-Jun-2022
-
Veranstaltungsort:
Berlin, Deutschland
-
Umfang:
8
-
Verlag:
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
Projekttitel:
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
