Search Results

Documents authored by de Vries, Mees

Artifact
Software
DOI: 10.4230/artifacts.22525
OCMu64

Authors: Ragnar Groot Koerkamp and Mees de Vries

Abstract
Cite as

Ragnar Groot Koerkamp, Mees de Vries. OCMu64 (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-22525,
   title = {{OCMu64}}, 
   author = {Groot Koerkamp, Ragnar and de Vries, Mees},
   note = {Software (visited on 2024-12-05)},
   url = {https://github.com/mjdv/ocmu64},
   doi = {10.4230/artifacts.22525},
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2024.35
PACE Solver Description: OCMu64, a Solver for One-Sided Crossing Minimization

Authors: Ragnar Groot Koerkamp and Mees de Vries

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract
Given a bipartite graph (A,B), the one-sided crossing minimization (OCM) problem is to find an ordering of the vertices of B that minimizes the number of edge crossings when drawn in the plane. We introduce the novel strongly fixed, practically fixed, and practically glued reductions that maximally generalize some existing reductions. We apply these in our exact solver OCMu64, that directly uses branch-and-bound on the ordering of the vertices of B and does not depend on ILP or SAT solvers.
Cite as

Ragnar Groot Koerkamp and Mees de Vries. PACE Solver Description: OCMu64, a Solver for One-Sided Crossing Minimization. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 35:1-35:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{grootkoerkamp_et_al:LIPIcs.IPEC.2024.35,
  author =	{Groot Koerkamp, Ragnar and de Vries, Mees},
  title =	{{PACE Solver Description: OCMu64, a Solver for One-Sided Crossing Minimization}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{35:1--35:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.35},
  URN =		{urn:nbn:de:0030-drops-222616},
  doi =		{10.4230/LIPIcs.IPEC.2024.35},
  annote =	{Keywords: Graph drawing, crossing number, branch and bound}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2020.29
PACE Solver Description: tdULL

Authors: Ruben Brokkelkamp, Raymond van Venetië, Mees de Vries, and Jan Westerdiep

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
We describe tdULL, an algorithm for computing treedepth decompositions of minimal depth. An implementation was submitted to the exact track of PACE 2020. tdULL is a branch and bound algorithm branching on inclusion-minimal separators.
Cite as

Ruben Brokkelkamp, Raymond van Venetië, Mees de Vries, and Jan Westerdiep. PACE Solver Description: tdULL. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 29:1-29:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{brokkelkamp_et_al:LIPIcs.IPEC.2020.29,
  author =	{Brokkelkamp, Ruben and van Veneti\"{e}, Raymond and de Vries, Mees and Westerdiep, Jan},
  title =	{{PACE Solver Description: tdULL}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{29:1--29:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.29},
  URN =		{urn:nbn:de:0030-drops-133326},
  doi =		{10.4230/LIPIcs.IPEC.2020.29},
  annote =	{Keywords: PACE 2020, treedepth, treedepth decomposition, vertex ranking, minimal separators, branch and bound}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact