Programme

Keynote speaker

Professor Tetsuo Asano

Computational Geometric and Combinatorial Approaches to Digital Halftoning

Digital halftoning is a technique to convert a continuous-tone image into a binary image consisting of black and white dots. It is an important technique for printing machines and printers to output an image with few intensity levels or colors which looks similar to an input image. In this talk I will explain how computational geometry and combinatorial optimization can contribute to digital halftoning or what geometric and combinatorial problems are related to digital halftoning.

Extended abstract

Timetable

Tuesday 10:30-12:00 CATS 1

Room: Wellington 2

• 10:30 Geometric spanners with few edges and degree five, Michiel Smid
• 11:00 Graph orientation algorithms to minimize the maximum outdegree, Yuichi Asahiro, Eiji Miyano, Hirotaka Ono and Kouhei Zenmyo
• 11:30 Multilayer Grid Embeddings of Iterated Line Digraphs, Toru Hasunuma

Tuesday 1:30-3:00 CATS 2

Room: Gallery

• 1:30 Compositional type systems for stack-based low-level languages, Ando Saabas and Tarmo Uustalu
• 2:00 Mechanically Verifying Correctness of CPS Compilation, Ye Henry Tian
• 2:30 Formalising the L4 microkernel API, Rafal Kolanski and Gerwin Klein

Tuesday 3:30-4:30 CATS 3 Keynote speaker

Room: Plenary Hall Computational Geometric and Combinatorial Approaches to Digital Halftoning, Tetsuo Asano

Tuesday 4:30-5:30

CATS business meeting

Wednesday 8:30-10:00 CATS 4

Room: Tasman B

• 8:30 Combinatorial Generation by Fusing Loopless Algorithms, Tadao Takaoka and Stephen Violich
• 9:00 The Busy Beaver, the Placid Platypus and Other Crazy Creatures, James Harland
• 9:30 A polynomial algorithm for codes based on directed graphs, Andrei Kelarev

Wednesday 10:30-12:00 CATS 5

Room: Tasman B

• 10:30 On the complexity of the DNA Simplified Partial Digest Problem, Jacek Blazewicz and Marta Kasprzak
• 11:00 On the Approximability of Maximum and Minimum Edge Clique Partition Problems, A. Dessmark, J. Jansson, A. Lingas, E.-M. Lundell and M. Persson 11:30 Faster Algorithms for Finding Missing Patterns, Shuai Cheng Li

Wednesday 1:30-3:00 CATS 6

Room: Tasman B

• 1:30 On the logical Implication of Multivalued Dependencies with Null Values, Sebastian Link
• 2:00 Boolean equation solving as graph traversal, Brian Herlihy, Peter Schachte and Harald Sondergaard
• 2:30 Learnability of Term Rewrite Systems from Positive Examples, M. R. K. Krishna Rao

Wednesday 3:30-4:30 CATS 7

Room: Tasman B

• 3:30 On-Demand Bounded Broadcast Scheduling with Tight Deadlines, Chung Keung Poon, Yinfeng Xu and Feifeng Zheng
• 4:00 Greedy algorithms for on-line set-covering and related problems, Giorgio Ausiello, Aristotelis Giannakos and Vangelis Paschos