Search Results

Documents authored by Feschet, Fabien


Document
CG Challenge
Shadoks Approach to Parallel Reconfiguration of Triangulations (CG Challenge)

Authors: Guilherme D. da Fonseca, Fabien Feschet, and Yan Gerard

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)


Abstract
We describe the methods used by Team Shadoks to win the CG:SHOP 2026 Challenge on parallel reconfiguration of planar triangulations. Our approach combines exact methods based on SAT with several greedy heuristics, and also makes use of SAT and MaxSAT for solution improvement.

Cite as

Guilherme D. da Fonseca, Fabien Feschet, and Yan Gerard. Shadoks Approach to Parallel Reconfiguration of Triangulations (CG Challenge). In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 107:1-107:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{dafonseca_et_al:LIPIcs.SoCG.2026.107,
  author =	{da Fonseca, Guilherme D. and Feschet, Fabien and Gerard, Yan},
  title =	{{Shadoks Approach to Parallel Reconfiguration of Triangulations}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{107:1--107:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.107},
  URN =		{urn:nbn:de:0030-drops-259130},
  doi =		{10.4230/LIPIcs.SoCG.2026.107},
  annote =	{Keywords: Exact algorithm, SAT, MaxSAT, heuristic, computational geometry}
}
Document
PACE Solver Description
PACE Solver Description: Shadoks Approach to Minimum Hitting Set and Dominating Set

Authors: Guilherme D. da Fonseca, Fabien Feschet, and Yan Gerard

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)


Abstract
Description of the solvers used by the Shadoks team in the PACE 2025 challenge. The challenge considers solvers for the minimum dominating set and hitting set problems. For the heuristic challenge, we respectively won third and fourth place for hitting set and dominating set. For the exact challenge, we won fifth place on both problems.

Cite as

Guilherme D. da Fonseca, Fabien Feschet, and Yan Gerard. PACE Solver Description: Shadoks Approach to Minimum Hitting Set and Dominating Set. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 34:1-34:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@InProceedings{dafonseca_et_al:LIPIcs.IPEC.2025.34,
  author =	{da Fonseca, Guilherme D. and Feschet, Fabien and Gerard, Yan},
  title =	{{PACE Solver Description: Shadoks Approach to Minimum Hitting Set and Dominating Set}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{34:1--34:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.34},
  URN =		{urn:nbn:de:0030-drops-251660},
  doi =		{10.4230/LIPIcs.IPEC.2025.34},
  annote =	{Keywords: Optimization, heuristic, hitting set, dominating set}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail