Special Issue “Selected Algorithmic Papers From CSR 2020”

The 15th International Computer Science Symposium in Russia (CSR 2020) was organized by the Ural Federal University located in Ekaterinburg, Russian Federation. This symposium traditionally covers a broad range of topics in Theoretical Computer Science, ranging from fundamental to application-related.

This Special Issue contains extended versions of selected contributions, having a clear algorithmic focus. They were previously presented at CSR 2020, see [1] for the whole proceedings. This selection still indicates the breadth of the research topics typically present at CSR conferences and hence possibly inspires the readers to choose CSR as a venue for publishing their own research.

Let us briefly describe the papers chosen for this Special Issue, in alphabetical order of their first authors:

• Costalonga, Kingan and Kingan [2] describe an algorithm to generate minimally 3-connected graphs, eliminating isomorphic duplicates using certificates generated by McKay’s isomorphism checker nauty.
• Genitrini and Pépin [3] consider unranking algorithms of combinations from a fairly general perspective, concerning arbitrary combinatorial objects and analyze their complexities both analytically and empirically.
• (Vector) subtraction games, also known as invariant games, can be seen as a variation of nim games. Gurvich and Vyalyi [4] show that there exist such games of finite dimension with a finite difference set that are EXP-complete.
• Niehren and Sakho [5] consider the problem of determinizing and minimizing automata for nested words in practice. They explain why the usual strategy fails and how to overcome this difficulty.
• Rupp and Funke [6] discuss two popular speed-up techniques for shortest path routing, contraction hierarchies as well as hub labels, and prove a square root lower bound on the query time.

We like to thank all referees that worked for this Special Issue, as well as the authors who extended their previously presented abstract to nice journal papers.

We hope that the readers of the Special Issue will enjoy these papers. If you like to read through other papers published at CSR and convince yourself both of the breadth and the depth of the submissions, we point once more to the conference proceedings of the 2020 edition [1], as well as to another selection of extended papers collected in a Special Issue to be published with Theory of Computing Systems in the very near future.