33rd International Workshop on Combinatorial Algorithms


  • The submission server is closed. Authors have been notified in early April, 2022.
  • Registration form   Registrations are now possible! Distinction: full (receiving proceedings), non-full and orthogonally: on-line and on-site. For instance: full on-site registration is 180 €.
  • There will be a Best Paper Award and a Best (Phd) Student Paper Award, both sponsored by Springer; details below
  • The list of accepted papers is displayed at the end of this page.
  • We will have a Special Issue with Algorithmica of full versions of selected papers

Venue (hybrid format)

  • University of Trier (June 7th - 9th, 2022), with live talks and discussions also transmitted to on-line participants
  • Graph- and Stringmasters on site: June 10th, 2022

Refined Venue of IWOCA and Graph- & Stringmasters

June 6th, 6.30 pm Get-together

June 7th, morning: 8.20 Registration, 9.00 Welcome / Opening, 9.20 4 Contributed Talks, 10.40 Break, 11.10 5 Contributed Talks

June 7th, afternoon: 2.00 Invited Talk of Erik Demaine, 3.30 Break, 4.00 5 Contributed Talks

June 8th, morning: 8.20 5 Contributed Talks, 10.00 Break, 10.30 Invited Talk of Akanksha Agrawal, 12.00 Presentation of Best Paper and Best Student Paper

June 8th, afternoon: Excursion, followed by a combined boat trip / conference dinner

June 9th, morning: 8.20 5 Contributed Talks, 10.00 Break, 10.30 5 Contributed Talks

June 9th, afternoon: 1.20 4 Contributed Talks, 3.00 Break, 3.30 Invited Talk of Bhaskar Ray Chaudhury, 5.00 Break, 5.15 Business Meeting

June 10th, morning: 08.20 Presentation of Open Problems and Group Formation, 10.00 Break, 10.30 First Working Session

June 10th, afternoon: 1.00 Recap / Second Working Session, 2.45 Break, 3.00 Third Working Session, 4.30 Break, 4.45 Result Announcements

Travel Tips

Important Dates (a.o.e.)

  • Abstract submission: January 6th, 2022  DONE
  • Paper submission: January 11th, 2022 DONE
  • Notification: April 4th, 2022 DONE


will be published within the LNCS series of Springer, within the ARCoSS subseries, as LNCS 13270. We therefore asked for submissions of original work in LNCS format, allowing for 12 pages plus bibliography and a possible, clearly marked appendix.

Invited Speakers

  • Akanksha Agrawal, IITM Chennai, India: Distance from Triviality 2.0: Hybrid Parameterizations
  • Erik Demaine, MIT, USA: Graphs as Algorithms: Characterizing Motion-Planning Gadgets through Simulation and Complexity
  • Bhaskar Ray Chaudhury, University of Illinois at Urbana Champaign, USA: On the Existence of EFX Allocations

List of Topics (Not Exclusive)

  • Algorithms and Data Structures
  • Algorithmic and Combinatorial Aspects of Cryptography and Information Security
  • Algorithmic Game Theory and Complexity of Games
  • Approximation Algorithms
  • Combinatorics and Graph Theory
  • Combinatorial Generation, Enumeration and Counting
  • Combinatorial Optimization
  • Combinatorics of Words
  • Complexity Theory
  • Computational Biology
  • Computational Geometry
  • Decompositions and Combinatorial Designs
  • Distributed, Parallel and Network Algorithms
  • Experimental Combinatorics
  • Fine-grained Complexity
  • Graph Algorithms and Modelling with Graphs
  • Graph Drawing and Graph Labelling
  • Network Theory and Temporal Graphs
  • Quantum Computing / Algorithms for Quantum Computers
  • Online Algorithms
  • Parameterized and Exact Algorithms
  • Probabilistic and Randomized Algorithms
  • Streaming Algorithms

Program Committee

  • Cristina Bazgan, University Paris Dauphine, France, Co-Chair
  • Henning Fernau, University of Trier, Germany, Co-Chair
  • Faisal Abu-Khzam, LAU Beirut, Lebanon
  • Jérémy Barbay, University of Chile, Santiago
  • Ljiljana Brankovic, University of Newcastle, Australia
  • Katrin Casel, HPI Potsdam, Germany
  • Katarína Cechlárová, University Košice, Slovakia
  • Charles Colbourn, Arizona State University, USA
  • Thomas Erlebach, Durham University, UK
  • Florent Foucaud, University Clermont Auvergne, France
  • Kshitij Gajjar, National University of Singapore
  • Adriana Hansberg, Instituto de Matemáticas, Universidad Nacional Autónoma de México
  • Toru Hasunuma, Tokushima University, Japan
  • Sun-Yuan Hsieh, National Cheng Kung University, Taiwan
  • Philipp Kindermann, Univesity of Trier, Germany
  • Gunnar Klau, University of Düsseldorf, Germany
  • Yasuaki Kobayashi, Kyoto University, Japan
  • Veli Mäkinen, University of Helsinki, Finland
  • Florin Manea, University of Göttingen, Germany
  • David Manlove, University of Glasgow, UK
  • André Nichterlein, TU Berlin, Germany
  • Mateus de Oliveira Oliveira, University of Bergen, Norway
  • Jakub Radoszewski, University of Warszawa, Poland
  • Giovanna Rosone, University of Pisa, Italy
  • Irena Rusu, University of Nantes, France
  • Jeffrey Shallit, University of Waterloo, Canada
  • Blerina Sinaimeri‬, LUISS University, Rome, Italy
  • Wing-Kin Sung, National University of Singapore
  • Sue Whitesides, University of Victoria, Canada
  • Meirav Zehavi, Ben-Gurion University of the Negev, Israel

Local Organizing Committee (preliminary)

  • Henning Fernau
  • Kevin Goergen
  • Philipp Kindermann
  • Kevin Mann
  • Norbert Müller
  • Esther Stürmer-Schwarz
  • Petra Wolf

Steering Committee

  • Maria Chudnovsky, Princeton University, USA
  • Costas Iliopoulos, King's Collega London, UK
  • Ralf Klasing, CNRS and University of Bordeaux, France
  • Wing-Kin Sung, National University of Singapore

List of accepted papers

The PC has also selected the Best Paper and the Best Student Paper. Congratulations!

  • Sreshth Aggarwal, Deepanjan Kesh, Divyam Singal: Lower Bounds for Restricted Schemes in the Two-Adaptive Bitprobe Model
  • Oswin Aichholzer, Ruy Fabila-Monroy, Philipp Kindermann, Irene Parada, Rosna Paul, Daniel Perz, Patrick Schnider, Birgit Vogtenhuber: Perfect Matchings with Crossings
  • Bogdan Alecu, Vladimir Alekseev, Aistis Atminas, Vadim Lozin, Viktor Zamaraev: Graph parameters, implicit representations and factorial properties
  • Giannis Alonistiotis, Antonis Antonopoulos, Nikolaos Melissinos, Aris Pagourtzis, Stavros Petakalis, Manolis Vasilakis: Approximating Subset Sum Ratio via Subset Sum Computations
  • Maxim Babenko, Stepan Artamonov: Faster Algorithm for Finding Maximum 1-Restricted Simple 2-Matchings
  • Janos Balogh, Gyorgy Dosa, Leah Epstein, Łukasz Jeż: Lower bounds on the performance of online algorithms for relaxed packing problems
  • Avah Banerjee: An Adjacency Labeling Scheme Based On A Decomposition Of Trees Into Caterpillars
  • Hideo Bannai, Tomohiro I, Tomasz Kociumaka, Dominik Köppl, Simon Puglisi: Computing Longest (Common) Lyndon Subsequence
  • Thais Bardini Idalino, Lucia Moura: Structure-aware combinatorial group testing: a new method for pandemic screening
  • Michael Bekos, Martin Gronemann, Fabrizio Montecchiani, Antonios Symvonis: Convex Grid Drawings of Planar Graphs with Constant Edge-Vertex Resolution
  • Pierre Bergé, Anthony Busson, Carl Feghali, Rémi Watrigant: 1-Extendability of independent sets
  • Daniel Bertschinger, Patrick Schnider, Jonas Passweg: Tukey Depth Histograms
  • Binay Bhattacharya, Amirhossein Mozafari, Thomas C. Shermer: An Efficient Algorithm for the Proximity Connected Two Center Problem
  • Cristiano Bocci, Chiara Capresi, Kitty Meeks, John Sylvester: A New Temporal Interpretation of Cluster Editing
  • Jan Bok, Jiri Fiala, Nikola Jedličková, Jan Kratochvil, Paweł Rzążewski: List covering of regular multigraphs
  • Elisabet Burjons, Janosch Fuchs, Henri Lotze: The Slotted Online One-Sided Crossing Minimization Problem on 2-Regular Graphs
  • Diane Castonguay, Erika Coelho, Hebert Coelho, Julliano Nascimento, Ueverton Souza: Perfect matching cuts partitioning a graph into complementary subgraphs
  • Andrea Caucchiolo, Ferdinando Cicalese: On the Intractability Landscape of Digraph Intersection Representations
  • Subhadeep Ranjan Dev, Sanjana Dey, Florent Foucaud, Ralf Klasing, Tuomo Lehtilä: The Red-Blue Separation problem on graphs
  • Pål Grønås Drange, Irene Muzi, Felix Reidl: Harmless Sets in Sparse Classes
  • Jaroslav Garvardt, Christian Komusiewicz, Frank Sommer: The Parameterized Complexity of s-Club with Triangle and Seed Constraints
  • Tomohiro I, Dominik Köppl: Space-Efficient B Trees via Load-Balancing
  • Asei Inoue, Yusuke Kobayashi: An Additive Approximation Scheme for the Nash Social Welfare Maximization with Identical Additive Valuations
  • Joanna Kaczmarek, Jörg Rothe: Controlling Weighted Voting Games by Deleting or Adding Players with or without Changing the Quota
  • Sung-Hwan Kim, Hwan Gue Cho: Practical Space-Efficient Index for Structural Pattern Matching
  • Paul Lapey, Aaron Williams: A Shift Gray Code for Fixed-Content Lukasiewicz Words
  • Jonas Lingg, Mateus de Oliveira Oliveira, Petra Wolf: Learning from Positive and Negative Examples: Dichotomies and Parameterized Algorithms
  • Felicia Lucke, Felix Mann: Using Edge Contractions and Vertex Deletions to Reduce the Independence Number and the Clique Number
  • Takuya Mieno, Mitsuru Funakoshi: Shortest Unique Palindromic Substring Queries in Semi-dynamic Settings
  • Soumen Nandi, Sagnik Sen, S Taruni: On relative clique number of triangle-free planar colored mixed graphs
  • Thi Huyen Chau Nguyen, Werner Grass, Klaus Jansen: Exact Polynomial Time Algorithm for the Response Time Analysis of Harmonic Tasks
  • Charis Papadopoulos, Spyridon Tzimas: Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage
  • Nicola Rizzo, Veli Mäkinen: Linear Time Construction of Indexable Elastic Founder Graphs
  • Jannik Schestag, Niels Grüttemeier, Christian Komusiewicz, Frank Sommer: On Critical Node Problems with Vulnerable Vertices
  • Kanae Yoshiwatari, Hironori Kiya, Tesshu Hanaka, Hirotaka Ono: Winner Determination Algorithms for Graph Games with Matching Structures


Explanation for eligibility of student paper:

To be eligible for the best student paper award, at least one of the paper authors must be a full-time (PhD) student at the time of submission, and the student(s) must have made a significant contribution to the paper.

Explanation of submissions of original papers

First of all, this means that the contents of a submitted paper must not have been published elsewhere, with a peer review process involved.  Hence, do not send your paper to a journal prior to the notification of authors of the conference. Then, there is no doubt about the originality of the paper’s content. There is no need to wait until the paper has been presented at the conference, although it is recommended waiting for this event, as sometimes authors receive additional feedback from the audience that is helpful for preparing the journal submission. This is why in Theoretical Computer Science, the current workflow seems to be to first put a technical report version of a paper on ArXive, then submit a short version to some conference, which might also lead to some updates of the ArXive version, and finally submit the full paper to a journal. Also, mind the possibility of being selected for the Special Issue of Algorithmica.

Springer Logo