IWOCA 2018: 29th International Workshop on Combinational Algorithms
National University of Singapore
Singapore, July 16-19, 2018

IWOCA2018 Technical session

Venue: SR1, 2nd floor, COM1, School of Computing, 13 Computing Drive, Singapore

Day 1: 16 July (Monday)

14:45-15:15 Registration
15:15-15:30 Opening session
15:30-16:30 StringMasters session
16:30-18:00 Session 1
18:00-20:00 Reception


Day 2: 17 July (Tuesday)

08:30-10:30 Session 2
10:30-11:00 Tea
11:00-12:00 Invited talk 1
12:00-13:30  Lunch + poster session
13:30-15:30 Session 3
15:30-16:00 Tea
16:00-18:00 Session 4


Day 3: 18 July (Wednesday)

08:30-10:00 Session 5
10:00-10:30 Tea
10:30-11:30 Invited talk 2
11:30-12:30  Session 6
12:30-12:45 Photo taking
12:45-14:15 Lunch
14:15-18:00  Excursion
18:00-20:00   Banquet


Day 4: 19 July (Thursday)

08:30-10:30 Session 7
10:30-11:00 Tea
11:00-12:00 Invited Talk 3
12:00-13:30 Lunch
13:30-15:30 Session 8
13:30-16:00 Tea
16:00-17:30 Session 9
17:30-17:45 Closing session


StringMasters session (16 July)
Chair: Gabriele Fici and Dalibor Froncek


Session 1: Graph drawing (16 July)
Chair: TBC

On the Area Requirements of Straight-Line Orthogonal Drawings of Ternary Trees
Barbara Covella, Fabrizio Frati and Maurizio Patrignani

The Crossing Number of Seq-Shellable Drawings of Complete Graphs
Petra Mutzel and Lutz Oettershagen

Placing Segments On Parallel Arcs
Yen Kaow Ng, Wenlong Jia and Shuai Cheng Li


Session 2: Compression (17 July)
Chair: TBC

Zero-Suppression and Computation Models
Hiroki Morizumi

An Efficient Representation of Partitions of Integers
Kentaro Sumigawa and Kunihiko Sadakane

LZ-ABT: A Practical Algorithm for ∝-Balanced Grammar Compression
Tatsuya Ohno, Keisuke Goto, Yoshimasa Takabatake, Tomohiro I and Hiroshi Sakamoto

Faster Coreset Construction for Projective Clustering via Low-Rank Approximation
Rameshwar Pratap and Sandeep Sen

Invited talk 1 (17 July)
Chair: TBC

Range Minimum Queries and Applications
Kunihiko Sadakane

Session 3: Combinatorics (17 July)
Chair: TBC

Linear clique-width of bi-complement reducible graphs
Bogdan Alecu, Vadim Lozin and Viktor Zamaraev

Linear Ramsey numbers
Aistis Atminas, Vadim Lozin and Viktor Zamaraev

On the Expected Number of Distinct Gapped Palindromic Factors
Philippe Duchon and Cyril Nicaud

Efficient Enumeration of Subgraphs and Induced Subgraphs with Bounded Girth
Kazuhiro Kurita, Kunihiro Wasa, Alessio Conte, Takeaki Unoand Hiroki Arimura

Session 4: Applications of combinatorics (17 July) 
Chair: TBC

Evaluation of Tie-breaking and Parameter ordering for the IPO Family of Algorithms used in Covering Array Generation
Kristoffer Kleine, Ilias Kotsireas and Dimitris E. Simos

Separating Interaction Effects Using Locating and Detecting Arrays
Stephen Seidel, Kaushik Sarkar, Charles Colbourn and Violet Syrotiuk

Minimum Polygons for Fixed Visibility VC-Dimension
Moritz Beck and Sabine Storandt

How far from a worst solution a random solution of a k-CSP instance can be?
Sophie Toulouse and Jean-François Culus

Session 5: Solving NP-hard problems (18 July)
Chair: TBC

Median of 3 Permutations, 3-Cycles and 3-Hitting Set Problem
Robin Milosz, Sylvie Hamel and Adeline Pierrot

Covering with Clubs: Complexity and Approximability
Riccardo Dondi, Giancarlo Mauri, Florian Sikora and Italo Zoppis

Structural Parameterizations for Colorful Components
Neeldhara Misra

Invited talk 2 (18 July)
Chair: TBC

Some Recent New Directions in Multivariate Algorithmics
Michael Fellows

Session 6: Pattern finding (18 July)
Chair: TBC

Pattern matching for $k$-track permutations
Laurent Bulteau, Romeo Rizzi and Stéphane Vialette

Fully leafed induced subtrees
Alexandre Blondin Massé, Julien de Carufel, Alain Goupil, Mélodie Lapointe, Émile Nadeau and Elise Vandomme

Session 7: Routing (19 July)  
Chair: TBC

Approximation algorithms for the $p$-hub center routing problem in parameterized metric graphs
Li-Hsuan Chen, Sun-Yuan Hsieh, Ling-Ju Hung and Ralf Klasing

Collision-free Routing Problem with Restricted L-path
Jammigumpula Ajay and Sasanka Roy

Minsum $k$-Sink Problem on Dynamic Flow Path Networks
Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda and Naoki Katoh

Branch-and-bound algorithm for Symmetric Travelling Salesman Problem
Alexey Nikolaev and Mikhail Batsyn

Invited talk 3 (19 July)
Chair: TBC

Survey of some recent near polynomial time results for Parity Games
Sanjay Jain

Session 8: Graph (19 July)
Chair: TBC

Graphs that are Not Pairwise Compatible: A New Proof Technique (Extended Abstract)
Pierluigi Baiocchi, Tiziana Calamoneri, Angelo Monti and Rossella Petreschi

A Fixed-Parameter Algorithm for the Max-Cut Problem on Embedded 1-Planar Graphs
Christine Dahn, Nils M. Kriege and Petra Mutzel

Computational Complexity of Robot Arm Simulation Problems
Tianfeng Feng, Takashi Horiyama, Yoshio Okamoto, Yota Otachi, Toshiki Saitoh, Takeaki Uno and Ryuhei Uehara

An Optimal Algorithm for Online Prize-collecting Node-weighted Steiner Forest
Christine Markarian

Session 9: Security (19 July)
Chair: TBC

Analysis of Information Leakage due to Operative Errors in Card-based Protocols
Takaaki Mizuki and Yuichi Komano

Cryptographic limitations on polynomial-time a posteriori query learning
Mikito Nanashima

Efficient Unbounded Fault-Tolerant Aggregate Signatures Using Nested Cover-Free Families
Thaís Bardini Idalino and Lucia Moura