
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 (3140) 
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 update 
Gonzalo Navarro 
See paper "Wee LCP" by Johannes Fischer, IPL 110(89):317320 (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

