Search Results

Documents authored by Jünger, Paul J.

Artifact
Software
DOI: 10.4230/artifacts.22523
PACE2024

Authors: Michael Jünger, Paul J. Jünger, Petra Mutzel, and Gerhard Reinelt

Abstract
Cite as

Michael Jünger, Paul J. Jünger, Petra Mutzel, Gerhard Reinelt. PACE2024 (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@misc{GitHub_OSCM_2024,
   title = {{PACE2024}}, 
   author = {J\"{u}nger, Michael and J\"{u}nger, Paul J. and Mutzel, Petra and Reinelt, Gerhard},
   note = {Software, version 1.0. (visited on 2024-12-05)},
   url = {https://github.com/pauljngr/PACE2024},
   doi = {10.4230/artifacts.22523},
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2024.27
PACE Solver Description: Exact Solution of the One-Sided Crossing Minimization Problem by the MPPEG Team

Authors: Michael Jünger, Paul J. Jünger, Petra Mutzel, and Gerhard Reinelt

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

Abstract
This is a short description of our solver oscm submitted by our team MPPEG to the PACE 2024 challenge both for the exact track and the parameterized track, available at https://github.com/pauljngr/PACE2024 [Jünger et al., 2024] and https://doi.org/10.5281/zenodo.11546972 [Jünger et al., 2024].
Cite as

Michael Jünger, Paul J. Jünger, Petra Mutzel, and Gerhard Reinelt. PACE Solver Description: Exact Solution of the One-Sided Crossing Minimization Problem by the MPPEG Team. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 27:1-27:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{junger_et_al:LIPIcs.IPEC.2024.27,
  author =	{J\"{u}nger, Michael and J\"{u}nger, Paul J. and Mutzel, Petra and Reinelt, Gerhard},
  title =	{{PACE Solver Description: Exact Solution of the One-Sided Crossing Minimization Problem by the MPPEG Team}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{27:1--27:4},
  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.27},
  URN =		{urn:nbn:de:0030-drops-222539},
  doi =		{10.4230/LIPIcs.IPEC.2024.27},
  annote =	{Keywords: Combinatorial Optimization, Linear Ordering, Crossing Minimization, Branch and Cut, Algorithm Engineering}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.31
Revisiting ILP Models for Exact Crossing Minimization in Storyline Drawings

Authors: Alexander Dobler, Michael Jünger, Paul J. Jünger, Julian Meffert, Petra Mutzel, and Martin Nöllenburg

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Storyline drawings are a popular visualization of interactions of a set of characters over time, e.g., to show participants of scenes in a book or movie. Characters are represented as x-monotone curves that converge vertically for interactions and diverge otherwise. Combinatorially, the task of computing storyline drawings reduces to finding a sequence of permutations of the character curves for the different time points, with the primary objective being crossing minimization of the induced character trajectories. In this paper, we revisit exact integer linear programming (ILP) approaches for this NP-hard problem. By enriching previous formulations with additional problem-specific insights and new heuristics, we obtain exact solutions for an extended new benchmark set of larger and more complex instances than had been used before. Our experiments show that our enriched formulations lead to better performing algorithms when compared to state-of-the–art modelling techniques. In particular, our best algorithms are on average 2.6-3.2 times faster than the state-of-the-art and succeed in solving complex instances that could not be solved before within the given time limit. Further, we show in an ablation study that our enrichment components contribute considerably to the performance of the new ILP formulation.
Cite as

Alexander Dobler, Michael Jünger, Paul J. Jünger, Julian Meffert, Petra Mutzel, and Martin Nöllenburg. Revisiting ILP Models for Exact Crossing Minimization in Storyline Drawings. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 31:1-31:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dobler_et_al:LIPIcs.GD.2024.31,
  author =	{Dobler, Alexander and J\"{u}nger, Michael and J\"{u}nger, Paul J. and Meffert, Julian and Mutzel, Petra and N\"{o}llenburg, Martin},
  title =	{{Revisiting ILP Models for Exact Crossing Minimization in Storyline Drawings}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{31:1--31:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.31},
  URN =		{urn:nbn:de:0030-drops-213159},
  doi =		{10.4230/LIPIcs.GD.2024.31},
  annote =	{Keywords: Storyline drawing, crossing minimization, integer linear programming, algorithm engineering, computational experiments}
}
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