<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
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.rights.license
Creative Commons Namensnennung 4.0 International
de
dc.rights.license
Creative Commons Attribution 4.0 International
en
dc.contributor.editoraffiliation
Université de Lorraine, CNRS, Inria, LORIA, Nancy, France