Session 1 - A

Exact Algorithms

(Takeshi Tokuyama)

8:00 - 8:22

N. Bourgeois, F. Della Croce*, B. Escoffier, and V. Th. Paschos, Exact Algorithms for Dominating Clique Problems.

8:22 - 8:44

Tomoki Imada*, Shunsuke Ota, Hiroshi Nagamochi, and Tatsuya Akutsu, Enumerating Stereoisomers of Tree Structured Molecules Using Dynamic Programming.

8:44 - 9:06

Sang Won Bae, Sunghee Choi, Chunseok Lee*, and Shin-ichi Tanigawa, Exact Algorithms for the Bottleneck Steiner Tree Problem.

9:06 - 9:28

Qiang-Sheng Hua , Dongxiao Yu*, Francis C.M. Lau, and Yuexuan Wang, Exact Algorithms for Set Multicover and Multiset Multicover Problems.

9:28 - 9:50

Francisco Claude, Reza Dorrigiv, Stephane Durocher, Robert Fraser*, Alejandro López-Ortiz, and Alejandro Salinger, Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm.

Session 1 - B

Approximation Algorithm

(Ding-Zhu Du)

8:00 - 8:22

Kazumasa Okumoto, Takuro Fukunaga*, and Hiroshi Nagamochi, Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems. 

8:22 - 8:44

Shuai Cheng Li* and Yen Kaow Ng, On Protein Structure Alignment under Distance Constraint.

8:44 - 9:06

Nikhil Bansal, Alberto Caprara, Klaus Jansen, Lars Prädel*, and Maxim Sviridenko, A Structural Lemma in 2-Dimensional Packing, and its Implications on Approximability.

9:06 - 9:28

Telikepalli Kavitha* and Julián Mestre, Max-coloring Paths: Tight Bounds and Extensions.

9:28 - 9:50

Yam Ki Cheung* and Ovidiu Daescu, Fréchet Distance Problems in Weighted Regions.

Session 1 - C

Complexity

(Oscar H. Ibarra)

8:00 - 8:22

Daniel Andersson and Peter Bro Miltersen*, The Complexity of Solving Stochastic Games on Graphs.

8:22 - 8:44

Chuzo Iwamoto*, Kento Sasaki, Kenji Nishio, and Kenichi Morita, Computational Complexity of Cast Puzzles.

8:44 - 9:06

Adrian Dumitrescu and Csaba D. Tóth*, New Bounds on the Average Distance from the Fermat-Weber Center of a Planar Convex Body.

9:06 - 9:28

Shiteng Chen, Zhiyi Huang, and Sampath Kannan*, Reconstructing Numbers from Pairwise Function Values.

9:28 - 9:50

Kristoffer Arnsfelt Hansen*, Oded Lachish, and Peter Bro Miltersen, Hilbert’s Thirteenth Problem and Circuit Complexity.

Coffee Break

9:50 - 10:05

Ilima Room

Session 2 - A

Data Structure

(Bethary My Chan)

10:05 - 10:27

Jens M. Schmidt*, Interval Stabbing Problems in Small Integer Ranges.

10:27 - 10:49

Gerth Stølting Brodal, Rolf Fagerberg, Mark Greve*, and Alejandro López-Ortiz, Online Sorted Range Reporting.

10:49 - 11:11

Yakov Nekrich*, Data Structures for Approximate Orthogonal Range Counting.

11:11 - 11:33

Gerth Stølting Brodal, Alexis C. Kaporis, Spyros Sioutas, Konstantinos Tsakalidis*, and Kostas Tsichlas, Dynamic 3-sided Planar Range Queries with Expected Doubly Logarithmic Time.

11:33 - 11:55

Diego Arroyuelo, Francisco Claude, Reza Dorrigiv, Stephane Durocher, Meng He, Alejandro López-Ortiz, J. Ian Munro, Patrick K. Nicholson, Alejandro Salinger, and Matthew Skala*, Untangled Monotonic Chains and Adaptive Range Search.

Session 2 - B

Computational Geometry

(Ovidiu Daescu)

10:05 - 10:27

Sanjiv Kapoor and Xiang-Yang Li*, Geodesic Spanners on Polyhedral Surfaces.

10:27 - 10:49

Danny Z. Chen and Haitao Wang*, Approximating Points by a Piecewise Linear Function: I.

10:49 - 11:11

Danny Z. Chen and Haitao Wang*, Approximating Points by a Piecewise Linear Function: II. Dealing with Outliers.

11:11 - 11:33

Jinhui Xu*, Lei Xu, and Evanthia Papadopoulou, Computing the Map of Geometric Minimal Cuts.

11:33 - 11:55

Rudolf Fleischer and Yihui Wang*, On the Camera Placement Problem.

Session 2 - C

Graph Theory

(Hong Zhu)

10:05 - 10:27

Takuro Fukunaga*, Graph Orientations with Set Connectivity Requirements.

10:27 - 10:49

Fedor V. Fomin, Serge Gaspers*, Saket Saurabh, and Stéphan Thomassé, A Linear Vertex Kernel for Maximum Internal Spanning Tree.

10:49 - 11:11

Dae Young Seo*, D. T. Lee, and Tien-Ching Lin, Geometric Minimum Diameter Minimum Cost Spanning Tree Problem.

11:11 - 11:33

Yusuke Kobayashi* and Christian Sommer, On Shortest Disjoint Paths in Planar Graphs.

11:33 - 11:55

Tai-Hsin Hsu* and Hsueh-I Lu, An Optimal Labeling for Node Connectivity.

Lunch

11:55 - 13:05

Ilima Room

Session 3 - A

Online Algorithm

(Kazuo Iwama)

13:05 - 13:27

Ping Xu* and XiangYang Li, SOFA: Strategyproof Online Frequency Allocation for Multihop Wireless Networks.

13:27 - 13:49

Francis Y.L. Chin*, Hing-Fung Ting, and Yong Zhang, 1-Bounded Space Algorithms for 2-Dimensional Bin Packing.

13:49 - 14:11

Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královic*, Richard Královic, and Tobias Mömke, On the Advice Complexity of Online Problems.

14:11 - 14:33

Xin Han* and Kazuhisa Makino, Online Knapsack Problems with Limited Cuts.

14:33 - 14:55

Annamaria Kovacs, Ulrich Meyer, Gabriel Moruz, and Andrei Negoescu*, Online Paging for Flash Memory Devices.

Session 3 - B

Approximation Algorithm

(Jin-Yi Cai)

13:05 - 13:27

Imran A. Pirwani*, Shifting Strategy for Geometric Graphs Without Geometry.

13:27 - 13:49

Minming Li*, Approximation Algorithms for Variable Voltage Processors: Min Energy, Max Throughput and Online Heuristics.

13:49 - 14:11

Zhou Xu and Liang Xu*, Approximation Algorithms for Min-max Path Cover Problems with Service Handling Time.

14:11 - 14:33

Sándor P. Fekete, Joseph S. B. Mitchell, and Christiane Schmidt*, Minimum Covering with Travel Cost.

14:33 - 14:55

Takehiro Ito, Yuichiro Miyamoto, Hirotaka Ono*, Hisao Tamaki, and Ryuhei Uehara, Route-Enabling Graph Orientation Problems.

Session 3 - C

Complexity

(Weili Wu)

13:05 - 13:27

Khaled Elbassioni* and Hans Raj Tiwary, Complexity of Approximating the Vertex Centroid of a Polyhedron.

13:27 - 13:49

Telikepalli Kavitha and Meghana Nasre*, Popular Matchings with Variable Job Capacities.

13:49 - 14:11

Shengyu Zhang*, On the Tightness of the Buhrman-Cleve-Wigderson Simulation.

14:11 - 14:33

Johannes Schneider* and Roger Wattenhofer, Bounds on Contention Management Algorithms.

14:33 - 14:55

Jean Cardinal, Erik D. Demaine, Martin L. Demaine, Shinji Imahori, Stefan Langerman, and Ryuhei Uehara*, Algorithmic Folding Complexity.

Coffee Break

14:55 - 15:10

Ilima Room

Session 4 - A

Optimization

(Takuro Fukunaga)

15:10 - 15:32

Weiwei Wu*, Minming Li, and Enhong Chen, Min-Energy Scheduling for Aligned Jobs in Accelerate Model.

15:32 - 15:54

Toshimasa Ishii* and Kazuhisa Makino, Posi-modular Systems with Modulotone Requirements under Permutation Constraints.

15:54 - 16:16

Deepanjan Kesh* and Shashank K. Mehta, Generalized Reduction to Compute Toric Ideals.

16:16 - 16:38

Li Chen and Bin Fu*, Linear and Sublinear Time Algorithms for Basis of Abelian Groups.

16:38 - 17:00

Raphael Eidenbenz* and Roger Wattenhofer, Good Programming in Transactional Memory: Game Theory Meets Multicore Architecture.

Session 4 - B

Complexity

(Kyung-Yong Chwa)

15:10 - 15:32

Petr A. Golovach, Marcin Kaminski*, Daniël Paulusma, and Dimitrios M. Thilikos, Induced Packing of Odd Cycles in a Planar Graph.

15:32 - 15:54

Naoki Katoh and Shin-ichi Tanigawa*, On the Infinitesimal Rigidity of Bar-and-slider Frameworks.

15:54 - 16:16

Paola Flocchini, Bernard Mans*, and Nicola Santoro, Exploration of Periodically Varying Graphs.

16:16 - 16:38

Jiong Guo, Rolf Niedermeier, and Ondrej Suchy*, Parameterized Complexity of Arc-Weighted Directed Steiner Problems.

16:38 - 17:00

Yoshitaka Nakao* and Hiroshi Nagamochi, Worst Case Analysis for Pickup and Delivery Problems with Consecutive Pickups and Deliveries.

Session 4 - C

Graph Theory

(Shlomo Moran)

15:10 - 15:32

Tsung-Hao Liu and Hsueh-I Lu*, Minimum Cycle Bases of Weighted Outerplanar Graphs.

15:32 - 15:54

Petr Golovach, Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov, Daniel Meister*, and Saket Saurabh, Bandwidth on AT-free graphs.

15:54 - 16:16

Jiong Guo, Iyad A. Kanj, Christian Komusiewicz*, and Johannes Uhlmann, Editing Graphs into Disjoint Unions of Dense Clusters.

16:16 - 16:38

Daniel Bruce, Chính T. Hoàng*, and Joe Sawada, A Certifying Algorithm for 3-Colorability of P5-Free Graphs.

16:38 - 17:00

Takehiro Ito*, Marcin Kaminski, Daniël Paulusma, and Dimitrios M. Thilikos, Parameterizing Cut Sets in a Graph by the Number of Their Components.

Keynote 1
(Oscar H. Ibarra)

8:30-9:30

Ronald L. Graham, Bubblesort and Juggling Sequences

Coffee Break

9:30-9:50

Garden Lanai Room

Keynote 2
(Ding-Zhu Du)

9:50-10:50

Naoki Katoh, A Proof of the Molecular Conjecture

Session 5 - A

Complexity

(Xiaoming Sun)

8:00 - 8:22

Minghui Jiang*, Inapproximability of Maximal Strip Recovery.

8:22 - 8:44

Marek Karpinski*, Andrzej Rucinski, and Edyta Szymanska, The Complexity of Perfect Matching Problems on Dense Hypergraphs.

8:44 - 9:06

V. Arvind, Pushkar S. Joglekar, and Srikanth Srinivasan*, On Lower Bounds for Constant Width Arithmetic Circuits.

9:06 - 9:28

Xi Chen and Shang-Hua Teng*, Spending is not Easier than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria.

9:28 - 9:50

Paul C. Bell and Igor Potapov*, The Identity Correspondence Problem and its Applications.

Session 5 - B

Approximation Algorithm

(Hsu-Chun Yen)

8:00 - 8:22

Andrzej Czygrinow*, Michal Hanckowiak, and Edyta Szymanska, Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs.

8:22 - 8:44

Daisuke Yamaguchi*, Shinji Imahori, Ryuhei Miyashiro, and Tomomi Matsui, An Improved Approximation Algorithm for the Traveling Tournament Problem.

8:44 - 9:06

Shihong Xu* and Hong Shen, The Fault-Tolerant Facility Allocation Problem.

9:06 - 9:28

Minming Li*, Peng-Jun Wan, and Frances Yao, Tighter Approximation Bounds for Minimum CDS in Wireless Ad Hoc Networks.

9:28 - 9:50

Laurent Bulteau*, Guillaume Fertin, and Irena Rusu, Maximal Strip Recovery Problem with Gaps: Hardness and Approximation Algorithms.

Session 5 - C

Computational Geometry

(Bhaskar DasGupta)

8:00 - 8:22

Christian Knauer, Maarten Löffler, Marc Scherfenberg*, and Thomas Wolle, The Directed Hausdorff Distance between Imprecise Point Sets.

8:22 - 8:44

Gunnar Carlsson, Gurjeet Singh, and Afra Zomorodian*, Computing Multidimensional Persistence.

8:44 - 9:06

Danny Z. Chen* and Haitao Wang, Locating an Obnoxious Line among Planar Objects.

9:06 - 9:28

Paul Bonsma* and Felix Breuer, Finding Fullerene Patches in Polynomial Time.

9:28 - 9:50

Xiao Zhou* and Takao Nishizeki, Convex Drawings of Internally Triconnected Plane Graphs on O(n²) Grids.

Coffee Break

9:50 - 10:05

Garden Lanai Room

Session 6 - A

Network

(Minming Li)

10:05 - 10:27

Riko Jacob, Stephan Ritscher*, Christian Scheideler, and Stefan Schmid, A Self-Stabilizing and Local Delaunay Graph Construction.

10:27 - 10:49

Michael T. Goodrich and Darren Strash*, Succinct Greedy Geometric Routing in the Euclidean Plane.

10:49 - 11:11

Jonathan Kelner and Petar Maymounkov*, Electric Routing and Concurrent Flow Cutting.

11:11 - 11:33

Naoyuki Kamiyama* and Naoki Katoh, A Polynomial-Time Algorithm for the Universally Quickest Transshipment Problem in a Certain Class of Dynamic Networks with Uniform Path-Lengths.

11:33 - 11:55

Benjamin Doerr, Anna Huber, and Ariel Levavi*, Strong Robustness of Randomized Rumor Spreading Protocols.

Session 6 - B

Data Structure & Computational Geometry

(Marek Karpinski)

10:05 - 10:27

Gerth Stølting Brodal and Allan Grønlund Jørgensen*, Data Structures for Range Median Queries.

10:27 - 10:49

Siddhartha Sen* and Robert E. Tarjan, Deletion Without Rebalancing in Multiway Search Trees.

10:49 - 11:11

Gerth Stølting Brodal, Allan Grønlund Jørgensen, Gabriel Moruz*, and Thomas Mølhave, Counting in the Presence of Memory Faults.

11:11 - 11:33

Scott Schneider* and Michael Spertus, A Simple, Fast, and Compact Static Dictionary.

11:33 - 11:55

Therese Biedl, Stephane Durocher*, and Jack Snoeyink, Reconstructing Polygons from Scanner Data.

Session 6 - C

Graph Theory

(Danny Z. Chen)

10:05 - 10:27

Robert Franke, Ignaz Rutter*, and Dorothea Wagner, Computing Large Matchings in Planar Graphs with Fixed Minimum Degree.

10:27 - 10:49

Tamara Mchedlidze* and Antonios Symvonis, Crossing-Free Acyclic Hamiltonian Path Completion for Planar st-Digraphs.

10:49 - 11:11

Cristina Bazgan, Basile Couëtoux, and Zsolt Tuza*, Covering a Graph with a Constrained Forest.

11:11 - 11:33

Marwan Al-Jubeh, Mashhood Ishaque, Kristóf Rédei, Diane L. Souvaine, and Csaba D. Tóth*, Tri-Edge-Connectivity Augmentation for Planar Straight Line Graphs.

11:33 - 11:55

Seok-Hee Hong* and Hiroshi Nagamochi, Upward Star-shaped Polyhedral Graphs.

Lunch

11:55 - 13:05

Garden Lanai Room

Session 7 - A

Complexity

(Igor Potapov)

13:05 - 13:27

Linqing Tang*, Conditional Hardness of Approximating Satisfiable Max 3CSP-q.

13:27 - 13:49

Tomoyuki Yamakami*, The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata.

13:49 - 14:11

Dan Alistarh*, Seth Gilbert, Rachid Guerraoui, and Corentin Travers, Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement.

14:11 - 14:33

Ján Manuch*, Ladislav Stacho, and Christine Stoll, Step-Assembly with a Constant Number of Tile Types.

14:33 - 14:55

Donald Stanley and Boting Yang*, Lower Bounds on Fast Searching.

Session 7 - B

Algorithm
Design

(Csaba David Toth)

13:05 - 13:27

Elliot Anshelevich, Deeparnab Chakrabarty, Ameya Hate*, and Chaitanya Swamy, Approximation Algorithms for the Firefighter Problem: Cuts over Time and Submodularity.

13:27 - 13:49

Qian-Ping Gu* and Hisao Tamaki, Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n^1+ε) Time.

13:49 - 14:11

Anna Adamaszek*, Artur Czumaj, and Andrzej Lingas, PTAS for k-Tour Cover Problem on the Plane for Moderately Large Values of k.

14:11 - 14:33

Tien-Ching Lin* and D. T. Lee, Optimal Randomized Algorithm for the Density Selection Problem.

14:33 - 14:55

Decheng Dai and Rong Ge*, New Results on Simple Stochastic Games.

Session 7 - C

Data Management

(Meng He)

13:05 - 13:27

Bodo Manthey and Heiko Röglin*, Worst-Case and Smoothed Analysis of k-Means Clustering with Bregman Divergences.

13:27 - 13:49

Wing-Kai Hon*, Tak-Wah Lam, Rahul Shah, Siu-Lung Tam, and Jeffrey Scott Vitter, Succinct Index for Dynamic Dictionary Matching.

13:49 - 14:11

Hagai Cohen* and Ely Porat, Range Non-Overlapping Indexing.

14:11 - 14:33

Sang Won Bae and Yoshio Okamoto*, Querying Two Boundary Points for Shortest Paths in a Polygonal Domain.

14:33 - 14:55

Sylvain Guillemot* and Stéphane Vialette, Pattern Matching for 321-Avoiding Permutations.

Coffee Break

14:55 - 15:10

Garden Lanai Room

Session 8 - A

Optimization

(Qianping Gu)

15:10 - 15:32

Erik D. Demaine, Martin L. Demaine, Goran Konjevod*, and Robert J. Lang, Folding a Better Checkerboard.

15:32 - 15:54

Ping-Hui Hsu, Kuan-Yu Chen, and Kun-Mao Chao*, Finding All Approximate Gapped Palindromes.

15:54 - 16:16

George Karakostas*, General Pseudo-Random Generators from Weaker Models of Computation.

16:16 - 16:38

Toshiki Saitoh*, Yota Otachi, Katsuhisa Yamanaka, and Ryuhei Uehara, Random Generation and Enumeration of Bipartite Permutation Graphs.

16:38 - 17:00

R. Chandrasekaran and K. Subramani*, A Combinatorial Algorithm for Horn Programs.

Session 8 - B

Online Algorithm  
&
Image Processing

(Tien-Ching Lin)

15:10 - 15:32

Amotz Bar-Noy and Michael Lampis*, Online Maximum Directed Cut.

15:32 - 15:54

Minkyoung Cho*, David M. Mount, and Eunhui Park, Maintaining Nets and Net Trees under Incremental Motion.

15:54 - 16:16

Shivali Agarwal, Ankur Narang*, and Rudrapatna K. Shyamasundar, Distributed Scheduling of Parallel Hybrid Computations.

16:16 - 16:38

Lars Arge and Morten Revsbæk*, I/O-Efficient Contour Tree Simplification.

16:38 - 17:00

Jinhee Chun, Ryosei Kasai, Matias Korman, and Takeshi Tokuyama*, Algorithms for Computing the Maximum Weight Region Decomposable into Elementary Shapes.

Session 8 - C

Graph Theory

(Yoshio Okamoto)

15:10 - 15:32

Craig Dillabaugh, Meng He*, Anil Maheshwari, and Norbert Zeh, I/O and Space-Efficient Path Traversal in Planar Graphs.

15:32 - 15:54

Jin Wook Kim, Siwon Choi*, Joong Chae Na, and Jeong Seop Sim, Improved Algorithms for Finding Consistent Superstrings based on a New Graph Model.

15:54 - 16:16

Pei-Chi Huang*, Hsin-Wen Wei, Yen-Chiu Chen, Ming-Yang Kao, Wei-Kuan Shih, and Tsan-sheng Hsu, Two-Vertex Connectivity Augmentations for Graphs with a Partition Constraint.

16:16 - 16:38

Sylvain Guillemot, Jesper Jansson*, and Wing-Kin Sung, Computing a Smallest Multi-labeled Phylogenetic Tree from Rooted Triplets.

16:38 - 17:00

Daniël Paulusma* and Johan M.M. van Rooij, On Partitioning a Graph into Two Connected Subgraphs.