Thursday, June 30, 2016

[DMANET] IWOCA 2016 - Call for Participation

27th International Workshop on Combinatorial Algorithms (IWOCA 2016)

Helsinki, Finland, August 17–19, 2016 <>

**Early registration deadline July 1st**


August 17 (Wednesday)

8:30-8:55 Registration

8:55-9:00 Welcome

09:00-09:50 Invited talk: Leslie Anne Goldberg
Approximately counting list H-colourings

9:50-10:40 Session 1: Computational complexity

Guillaume Ducoffe, Sylvain Legay and Nicolas Nisse. On the complexity of computing the tree-breadth

Martin Böhm and Pavel Veselý. Online Chromatic Number is PSPACE-Complete

10:40-11:00 Coffee break

11:00-12:40 Session 2: Computational geometry

Radoslav Fulek. Bounded embeddings of graphs in the plane

Stefan Funke, Filip Krumpe and Sabine Storandt. Crushing Balls Efficiently

Prosenjit Bose, Jean-Lou De Carufel, Alina Shaikhet and Michiel Smid. Essential Constraints of Edge-Constrained Proximity Graphs

Ahmad Biniaz, Prosenjit Bose, Anil Maheshwari and Michiel Smid. Plane Bichromatic Trees of Low Degree

12:40-14:20 Lunch break

14:20-16:00 Session 3: Networks

Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi and Luca Versari. Directing Road Networks in Each Feasible Way

Gennaro Cordasco, Luisa Gargano, Adele Rescigno and Ugo Vaccaro. Evangelism in Social Networks

Gianlorenzo D'Angelo, Mattia D'Emidio and Daniele Frigioni. Distance Queries in Large-Scale Fully Dynamic Complex Networks

Yuya Higashikawa, Siu-Wing Cheng, Tsunehiko Kameda, Naoki Katoh and Shun Saburi. Minimax Regret 1-Median Problem in Dynamic Path Networks

16:00-16:20 Coffee break

16:20-17:35 Session 4: Enumeration

Tiziana Calamoneri, Mattia Gastaldello, Arnaud Mary, Marie-France Sagot and Blerina Sinaimeri. On Maximal Chain Subgraphs and Covers of Bipartite Graphs

Max Alekseyev. Weighted de Bruijn Graphs for the Menage Problem and Its Generalizations

Haruka Mizuta, Takehiro Ito and Xiao Zhou. Reconfiguration of Steiner Trees in an Unweighted Graph

August 18 (Thursday)

09:00-10:40 Session 1: Online algorithms

Joan Boyar, Lene M. Favrholdt, Christian Kudahl and Jesper W. Mikkelsen. Weighted Online Problems with Advice

Yuta Fujishige, Michitaro Nakamura, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda. Finding gapped palindromes online

Jhoirene Clemente, Christian Kudahl, Dennis Komm and Juraj Hromkovič. Advice Complexity of the Online Search Problem

Takuya Takagi, Shunsuke Inenaga, Kunihiko Sadakane and Hiroki Arimura. Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing

10:40-11:00 Coffee break

11:00-12:40 Session 2: Algorithmic graph theory

Hassan Aboueisha, Shahid Hussain, Vadim Lozin, Jerome Monnot, Bernard Ries and Viktor Zamaraev. A boundary property for upper domination

Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein,
Michael Lampis, Mathieu Liedloff, Jerome Monnot and Vangelis Paschos. Upper Domination: Complexity and Approximation

Konrad Kazimierz Dabrowski, Vadim Lozin and Daniel Paulusma. Well-quasi-ordering versus clique-width: new results on bigenic classes

Xujin Chen, Zhuo Diao, Xiaodong Hu and Zhongzheng Tang. Sufficient Conditions for Tuza's Conjecture on Packing and Covering Triangles

12:40-14:20 Lunch break

14:20-16:00 Invited talk: Giuseppe F. Italiano
2-Connectivity Problems in Directed Graphs

14:20-16:00 Session 3: Dynamic programming

Aravind N. R., Subrahmanyam Kalyanasundaram and Anjeneya Swami Kare. Linear Time Algorithms for Happy Vertex Coloring Problems for Trees

Pawel Gawrychowski and Łukasz Zatorski. Speeding up dynamic programming in the line-constrained k-median

16:00-16:20 Coffee break

16:20-17:10 Open problems session

18:00 Meet at excursion

20:00 Dinner at Walhalla on Suomenlinna

23:00 Transportation back to the city

August 19 (Friday)

09:00-10:40 Session 1: Combinatorial algorithms

Guillaume Blin, Marie Gasparoux, Sebastian Ordyniak and Alexandru Popa. SOBRA - Shielding Optimization for BRAchytherapy

Piotr Wojciechowski and K. Subramani. A bit-scaling algorithm for integer feasibility in UTVPI constraints

Markus Chimani, Ivo Hedtke and Tilo Wiedera. Limits of Greedy Approximation Algorithms for the Maximum Planar Subgraph Problem

Robert Benkoczi, Ram Dahal and Daya Gaur. Exact Algorithms For Weighted Coloring In Special Classes of Tree and Cactus Graphs

10:40-11:00 Coffee break

11:00-12:40 Session 2: Graph algorithms

Petr Golovach, Dieter Kratsch, Daniel Paulusma and Anthony Stewart. Finding Cactus Roots in Polynomial Time

Peter Damaschke. Computing Giant Graph Diameters

Martin Fürer. Faster Computation of Path-Width

Peter Damaschke. The Solution Space of Sorting with Recurring Comparison Faults

12:40-14:20 Lunch break

14:20-16:00 Invited talk: Petteri Kaski
Polynomial representations in algorithm design

14:20-16:00 Session 3: Combinatorics

Adrian Dumitrescu, Ritankar Mandal and Csaba Toth. Monotone paths in geometric triangulations

Andreas Baertschi, Barbara Geissmann, Daniel Graf, Tomas Hruz, Paolo Penna and Thomas Tschager. On computing the total displacement number via weighted Motzkin paths

16:00-16:20 Coffee break

16:20-17:10 Session 4: Probabilistics

Kaushik Sarkar, Charles J. Colbourn, Annalisa De Bonis and Ugo Vaccaro. Partial Covering Arrays: Algorithms and Asymptotics

Moritz von Looz and Henning Meyerhenke. Querying Probabilistic Neighborhoods in Spatial Data Sets Efficiently

17:10-17:15 Closing remarks


* Contributions to be spread via DMANET are submitted to
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.