Search Results

Documents authored by Mallem, Maher

Artifact
Software
DOI: 10.4230/artifacts.25783
KururinTAS

Authors: Mickaël Laurent and Maher Mallem

Abstract
Cite as

Mickaël Laurent, Maher Mallem. KururinTAS (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{kurubot,
   title = {{KururinTAS}}, 
   author = {Laurent, Micka\"{e}l and Mallem, Maher},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:38c9ece3ce3ee16ef48ecd29d110e056706aa8f2;origin=https://github.com/E-Sh4rk/KururinTAS;visit=swh:1:snp:46649a26917549f1c65d87d8566a9d1dc8d28092;anchor=swh:1:rev:4f723bd8399f62bfae9570f150dba5b42d87ef18}{\texttt{swh:1:dir:38c9ece3ce3ee16ef48ecd29d110e056706aa8f2}} (visited on 2026-05-15)},
   url = {https://github.com/E-Sh4rk/KururinTAS},
   doi = {10.4230/artifacts.25783},
}
Artifact
Software
DOI: 10.4230/artifacts.25784
Tool Assisted Speedrun - GBA Kuru Kuru Kururin by mohoc & E-Sh4rk in 06:11.59

Authors: Mickaël Laurent and Maher Mallem

Abstract
Cite as

Mickaël Laurent, Maher Mallem. Tool Assisted Speedrun - GBA Kuru Kuru Kururin by mohoc & E-Sh4rk in 06:11.59 (Software, Tool-Assisted Speedrun). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{TASany,
   title = {{Tool Assisted Speedrun - GBA Kuru Kuru Kururin by mohoc \& E-Sh4rk in 06:11.59}}, 
   author = {Laurent, Micka\"{e}l and Mallem, Maher},
   note = {Software (visited on 2026-05-15)},
   url = {https://tasvideos.org/3933M},
   doi = {10.4230/artifacts.25784},
}
Artifact
Software
DOI: 10.4230/artifacts.25785
Tool Assisted Speedrun - GBA Kuru Kuru Kururin "100%" by mohoc in 23:51.95

Authors: Maher Mallem

Abstract
Cite as

Maher Mallem. Tool Assisted Speedrun - GBA Kuru Kuru Kururin "100%" by mohoc in 23:51.95 (Software, Tool-Assisted Speedrun). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{TAS100,
   title = {{Tool Assisted Speedrun - GBA Kuru Kuru Kururin "100\%" by mohoc in 23:51.95}}, 
   author = {Mallem, Maher},
   note = {Software (visited on 2026-05-15)},
   url = {https://tasvideos.org/6116M},
   doi = {10.4230/artifacts.25785},
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.29
Finding Shortest Walks in Kuru Kuru Kururin

Authors: Mickaël Laurent and Maher Mallem

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
This paper serves as a celebration of the twenty-fifth anniversary of Kuru Kuru Kururin. Although this video game is presented as a collection of two-dimensional puzzles based on rotation, it naturally invites players to complete its levels as quickly as possible. This has led to a surprisingly rich and challenging playing field to finding foremost temporal walks. In this work, we tackle this problem both in theory and in practice. First, we introduce a model for the game and provide an in-depth complexity analysis. Most notably, we show how each gameplay mechanic independently brings a layer of NP-hardness and/or co-NP-hardness. We also provide a pseudo-polynomial time algorithm for the general problem and identify several cases which can be solved in polynomial time. Along the way, we discuss connections to the more established framework of temporal graphs, both in the point model and the interval model. Then, we propose simple and flexible algorithmic techniques to reduce state space and guide the search, offering trade-offs between precision and computation speed in practice. These techniques were implemented and tested using a full recreation of the game physics and the levels from the original game. We demonstrate the efficiency of our framework in several settings - with or without taking damage, with or without unintended game mechanics - and relate empirical struggles which we encountered in practice to our complexity analysis. Our implementation is open source and fully available online, offering a novel and amusing setting to benchmark shortest path algorithms.
Cite as

Mickaël Laurent and Maher Mallem. Finding Shortest Walks in Kuru Kuru Kururin. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{laurent_et_al:LIPIcs.FUN.2026.29,
  author =	{Laurent, Micka\"{e}l and Mallem, Maher},
  title =	{{Finding Shortest Walks in Kuru Kuru Kururin}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{29:1--29:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.29},
  URN =		{urn:nbn:de:0030-drops-257480},
  doi =		{10.4230/LIPIcs.FUN.2026.29},
  annote =	{Keywords: Shortest path, Complexity}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2022.21
Parameterized Complexity of a Parallel Machine Scheduling Problem

Authors: Maher Mallem, Claire Hanen, and Alix Munier-Kordon

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Abstract
In this paper we consider the parameterized complexity of two versions of a parallel machine scheduling problem with precedence delays, unit processing times and time windows. In the first version - with exact delays - we assume that the delay between two jobs must be exactly respected, whereas in the second version - with minimum delays - the delay between two jobs is a lower bound on the time between them. Two parameters are considered for this analysis: the pathwidth of the interval graph induced by the time windows and the maximum precedence delay value. We prove that our problems are para-NP-complete with respect to any of the two parameters and fixed-parameter tractable parameterized by the pair of parameters.
Cite as

Maher Mallem, Claire Hanen, and Alix Munier-Kordon. Parameterized Complexity of a Parallel Machine Scheduling Problem. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 21:1-21:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{mallem_et_al:LIPIcs.IPEC.2022.21,
  author =	{Mallem, Maher and Hanen, Claire and Munier-Kordon, Alix},
  title =	{{Parameterized Complexity of a Parallel Machine Scheduling Problem}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{21:1--21:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.21},
  URN =		{urn:nbn:de:0030-drops-173774},
  doi =		{10.4230/LIPIcs.IPEC.2022.21},
  annote =	{Keywords: parameterized complexity, scheduling, precedence delays, pathwidth, chains, parallel processors}
}
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
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact