International Workshop on Combinatorial Algorithms

Problems List

Dear Readers,

This is a non-exhaustive list of open problems contributed by the IWOCA community, often but not necessarily at the open problem session of the IWOCA conference.

If you know of any results relevant to one of the problems, also partial ones, we would greatly appreciate it if you could let us know. Please contact one of the problem section editors (Gabriele Fici: gabriele.fici_AT_unipa.it; Oliver Schaudt: schaudto_AT_uni-koeln.de)

If you have started working on a problem and made some advances, you could consider contacting the contributor of the problem, possibly but not necessarily with view of cooperating with him or her. In any case, we ask you to cite the IWOCA open problems page (www.iwoca.org, Problems Section) as well as the name of the problem contributor, should your work result in a publication.

If you have any open problems you would like to present to the IWOCA community, please don't hesitate to contact us (Gabriele Fici: gabriele.fici_AT_unipa.it; Oliver Schaudt: schaudto_AT_uni-koeln.de).


ARCHIVE
(problems that have been solved, or older versions of open problems)
 
Problem Contributed by in/at
last updated
 
LATEST PROBLEMS (IWOCA 2016) (check last column for update status)
Derangements with a Fixed Number of Inversions Max A. Alekseyev IWOCA 2016 Aug. 2016
Grammar-Based Compression Katrin Casel, Henning Fernau, Markus L. Schmid IWOCA 2016 Aug. 2016
The 3-Sphere Regular Cellulation Conjecture Sergio De Agostino IWOCA 2016 Aug. 2016
Sorting Strings by Reversals Guillaume Fertin IWOCA 2016 Aug. 2016
Does P-complete have a hierarchy like NP-complete has W[*]? Shouwei Li IWOCA 2016 Aug. 2016
Balanced Mobiles Yassine Hamoudi, Sophie Laplante, Roberto Mantaci IWOCA 2016 Aug. 2016
Can Lempel-Ziv and Burrows-Wheeler compression be asymptotically compared? Nicola Prezza IWOCA 2016 Aug. 2016
 
PROBLEMS FROM PREVIOUS IWOCA'S (check last column for update status)
Hamiltonian Paths in the Complete Graph Giuseppe Mazzuoccolo IWOCA 2015 Oct. 2015
Readability of bipartite graphs Martin Milanič IWOCA 2015 Oct. 2015
Computing The Palindromic Length Faster Arseny Shur IWOCA 2015 Oct. 2015
Vector connectivity with demands at most 3 Ferdinando Cicalese IWOCA 2015 Oct. 2015
Constructing sort of Δ-regular graphs to challenge the IRUP property for bin packing Romeo Rizzi IWOCA 2015 Oct. 2015
Counting numerical semigroups by genus Maria Bras-Amorós IWOCA 2014 Oct. 2014
Tiling hypercubes with copies of a given graph Jerrold R. Griggs IWOCA 2014 Dec. 2014
When is Size-One Memory Mastermind worse than original Mastermind? Gerold Jäger IWOCA 2014 Dec. 2014
On the Minimum Number of Plus Operators in Expressions of Series-Parallel Graphs and in Read-Once Functions Mark Korenblit,
Vadim E. Levit
IWOCA 2014 Oct. 2015
The maximum edge q-coloring problem Tommi Larjomaa,
Alexandru Popa
IWOCA 2014 Oct. 2015
Compute Runs/Repetitions Without Global Data Structures
In this talk there is more detailed info. See also the archive.
Bill Smyth IWOCA 2014 Oct. 2014
Problems on Minimal Pancyclic Graphs Walter Wallis IWOCA 2014 Oct. 2014
Decision of Soccer Score Sequences Péter Burcsi IWOCA 2013 Oct. 2015
Simply Connected Domino Tatami Covering Alejandro Erickson IWOCA 2013 Oct. 2015
Finding posets P in a family of subposets Jerrold R. Griggs IWOCA 2013 Aug. 2014
Maximum Rooted Triplets Consistency Jesper Jansson Sep. 2013 Oct. 2015
Complexity of Magic Labelling Gerold Jäger IWOCA 2013 Oct. 2015
The (2,1) Consecutive-Ones-Property Murray Patterson IWOCA 2013 Aug. 2014
The generelized inverse Voronoi problem Hebert Pérez-Rosés IWOCA 2013 July 2013
Complexity of Unshuffling a Square for Small Alphabets. More details also in IWOCA2103 slides (open problem on p.5). Michael Soltys IWOCA 2013 Oct. 2014
Decidability of set decipherability over directed figures Włodzimierz Moczurad IWOCA 2012 Oct. 2015
Tight bounds for sorting a multiset?Travis Gagie
 
IWOCA 2009 Oct. 2015
Graphs with no equal length cycles Chunhui Lai IWOCA 2007 Oct. 2015
The complexity of covering a ladder using cycles F. Foucaud IWOCA 2012 Oct. 2015
Element Uniqueness: A special case Tetsuo Asano
IWOCA 2011 Mar. 2013
A problem on domatic partition S. Arumugam IWOCA 2011 June 2011
Acyclic Coloring Subdivision Rahnuma Islam Nishat IWOCA 2011 Apr. 2012
The nth MARM: Maximum Red Matching Free of Blue-Red Alternating Cycles in a Complete Blue-Red Bipartite Graph of Degree n Vadim Timkovsky Jan. 2011 Jan. 2011
Distance magic graphs S. Arumugam IWOCA 2010 Jan. 2011
Distance pattern distinguishing sets in graphs S. Arumugam IWOCA 2009 Jan. 2011
Open problems in dynamic map labeling Chee Yap IWOCA 2007 Mar. 2012
Indexed approximate string matching
(Partial progress has been made here, but in general still open.)
Gonzalo Navarro Mar. 2013
Certificate dispersal problems Koichi Wada
 
IWOCA 2007
 
ARCHIVE
(problems that have been solved, or older versions of open problems)