|
|
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
update |
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
|
|
