International Workshop on Combinatorial Algorithms

Problems Archive

Here are some problems that have been presented on the IWOCA problems page and have either been solved or updated so thoroughly that they deserve a new presentation.

Problem Contributed by/in Comments
Arithmetic Progressions of String Data Structures Dominik Köppl
IWOCA 2019
Problem solved. See the paper: Jacqueline Daykin, Dominik Köppl, David Kübel, and Florian Stober. On Arithmetically Progressed Suffix Arrays, PSC 2020.
Computing The Palindromic Length Faster Arseny Shur
IWOCA 2015
Problem solved. See the paper Palindromic Length in Linear Time, CPM 2017.
Problems on prefix normal words Zsuzsanna Lipták
IWOCA 2014
Bounds have been substantially improved in: Timothy M. Chan, Moshe Lewenstein, Clustered Integer 3SUM via Additive Combinatorics. STOC 2015 (31-40)
A problem on maximum dense subgraphs Sergei Bezrukov
IWOCA 2014
Solved by Edouard Bonnet and Florian Sikora: A note on Edge Isoperimetric Numbers and Regular Graphs, IJFCS (to appear)
A nested recurrence relation with Fibonacci values at Fibonacci indices Frank Ruskey
IWOCA 2013
Solved by Peter Burcsi
Editing a Graph into a Clique and Isolated Vertices Peter Damaschke
IWOCA 2013
Solved in this paper: Ivan Kovác, Ivana Selecéniová, Monika Steinová: On the Clique Editing Problem, MFCS (2014)
Weighted Coloring Júlio Araújo,
IWOCA 2011
see paper on this problem (2013)
Does a polynomial maximising algorithm imply a polynomial minimising algorithm? Prabhu Manyem Solved in this paper (2012)
Entropy compressed suffix trees
Gonzalo Navarro See paper "Wee LCP" by Johannes Fischer, IPL 110(8-9):317-320 (2010)
The maximum number of runs in a string/ Overlapping squares in strings Bill Smyth, 2008, 2010 (E. Kopylova), 2011, 2012, 2013 See the problem Computing runs/repetitions without global data structures (IWOCA 2014) on the current problems page. Here are some earlier versions: The maximum number of squares in strings (2008 and Jan. 2011), and Aug. 2011. And a previous series of lectures on this topic given by Bill Smyth in Warsaw (May 2012): lecture1, lecture2, lecture3. Current version of problem explained in this talk (2014).
An open problem on identities in groups Sue Whitesides
IWOCA 2011
Back to Problem List