<div class="csl-bib-body">
<div class="csl-entry">Schidler, A. (2022). SAT-Based Local Search for Plane Subgraph Partitions. In X. Goaoc & M. Kerber (Eds.), <i>38th International Symposium on Computational Geometry (SoCG 2022)</i> (pp. 1–8). Schloss Dagstuhl --Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2022.74</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/150308
-
dc.description.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
dc.description.sponsorship
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.description.sponsorship
WWTF Wiener Wissenschafts-, Forschu und Technologiefonds
-
dc.language.iso
en
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
-
dc.subject
graph coloring
en
dc.subject
large neighborhood search
en
dc.subject
local improvement
en
dc.subject
logic
en
dc.subject
plane subgraphs
en
dc.subject
SAT
en
dc.subject
SLIM
en
dc.title
SAT-Based Local Search for Plane Subgraph Partitions
