Program
2021.10.25 (Mon.)

08:30-09:00 Registration
09:00-09:30 Opening
09:30-10:30 Keynote Speech #1 Prof. Ding-Zhu Du
(University of Texas at Dallas, USA)
Session Chair: Prof. Sun-Yuan Hsieh
10:30-10:45 Coffee/Tea Break
10:45-11:45 Keynote Speech #2 Prof. Takeshi Tokuyama
(Kwansei Gakuin University, Japan)
Session Chair: Prof. Sun-Yuan Hsieh
11:45-12:55 Lunch
12:55-13:25 A1-1 B1-1 C1-1
13:25-13:50 A1-2 B1-2 C1-2
13:50-14:15 A1-3 B1-3 C1-3
14:15-14:40 A1-4 B1-4 C1-4
14:40-15:05 A1-5 B1-5 C1-5
15:05-15:15 Coffee/Tea Break
15:15-15:45 A2-1 B2-1 C2-1
15:45-16:10 A2-2 B2-2 C2-2
16:10-16:35 A2-3 B2-3 C2-3
16:35-17:00 A2-4 B2-4 C2-4
17:00-17:25 A2-5 B2-5 C2-5

Session A1: Approximation Algorithms
Session Chair: Wing-Kai Hon
A1-1 Sheng-Yen Ko, Ho-Lin Chen, Siu-Wing Cheng, Wing-Kai Hon and Chung-Shou Liao, General Max-Min Fair Allocation.
A1-2 Tom Davot, Lucas Isenmann and Jocelyn Thiebaut, On the approximation hardness of geodetic set and its variants.
A1-3 Liam Roditty and Roei Tov, Approximate Distance Oracles with Improved Stretch for Sparse Graphs.
A1-4 Pooja Goyal and B S Panda, Hardness and Approximation Results of Roman {3}-Domination in Graphs.
A1-5 Richard Spence, Stephen Kobourov and Faryad Sahneh, Approximation algorithms for priority Steiner tree problems.
Session B1: Recreational Games
Session Chair: Ho-Lin Chen
B1-1 Suthee Ruangwises, Two Standard Decks of Playing Cards are Sufficient for a ZKP for Sudoku.
B1-2 Win Hlaing Hlaing Myint, Ryuhei Uehara and Giovanni Viglietta, Token Shifting on Graphs.
B1-3 Masaaki Kanzaki, Yota Otachi and Ryuhei Uehara, Computational Complexity of Jumping Block Puzzles.
B1-4 Raimu Isuzugawa, Kodai Toyoda, Yu Sasaki, Daiki Miyahara and Takaaki Mizuki, A Card-minimal Three-Input AND Protocol Using Two Shuffles.
B1-5 Eurinardo Costa, Nicolas Martins and Rudini Sampaio, Spy game: FPT-algorithm and results on graph products.
Session C1: Computational Geometry
Session Chair: Meng-Tsung Tsai
C1-1 Stephane Durocher, Mark Keil and Debajyoti Mondal, Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set.
C1-2 Shin-Ichi Nakano, The Coverage problem by Aligned Disks.
C1-3 Yannick Bosch, Peter Schäfer, Joachim Spoerhase, Sabine Storandt and Johannes Zink, Consistent Simplification of Polyline Tree Bundles.
C1-4 Yuki Kobayashi, Yuya Higashikawa and Naoki Katoh, Improving Upper and Lower Bounds for the Total Number of Edge Crossings of Euclidean Minimum Weight Laman Graphs.
C1-5 Ankush Acharyya, Ramesh Jallu, Vahideh Keikha, Maarten Löffler and Maria Saumell, Minimum Color Spanning Circle in Imprecise Setup.
Session A2: Algorithms
Session Chair: Ralf Klasing
A2-1 Edward Pyne and Salil Vadhan, Limitations of the Impagliazzo-Nisan-Wigderson Pseudorandom Generator against Permutation Branching Programs.
A2-2 Dong Xiang and Yunzhou Ju, All-to-All Broadcast in Dragonfly Networks.
A2-3 Chun Lin, Chao-Yuan Huang and Ming-Jer Tsai, An Efficient Algorithm for Enumerating Longest Common Increasing Subsequences.
A2-4 Bugra Caskurlu, Ozgun Ekici and Fatih Erdem Kizilkaya, On Singleton Congestion Games with Resilience Against Collusion.
A2-5 Ben Cameron, Aaron Grubb and Joe Sawada, A Pivot Gray Code Listing for the Spanning Trees of the Fan Graph.
Session B2: Online Algorithm and Streaming Algorithms
Session Chair: Peter Rossmanith
A2-1 T-H. Hubert Chan and Chui Shan Lee, On the Hardness of Opinion Dynamics Optimization with L1-Budget on Varying Susceptibility to Persuasion.
B2-2 Vladimir Braverman, Viska Wei and Samson Zhou, Symmetric Norm Estimation and Regression on Sliding Windows.
B2-3 Cheng-Hung Chiang and Meng-Tsung Tsai, Single-Pass Streaming Algorithms to Partition Graphs into Few Forests.
B2-4 Elisabet Burjons, Matthias Gehnen, Henri Lotze, Daniel Mock and Peter Rossmanith, The Secretary Problem with Reservation Costs.
B2-5 Songhua Li, Minming Li, Lingjie Duan and Victor C.S. Lee, Online Ride-Hitching in UAV Travelling.
Session C2: Computational Geometry & Parameterized
Complexity and Algorithms
Session Chair: Ching-Lueh Chang
C2-1 Ching-Lueh Chang, Deterministic metric 1-median selection with a 1-o(1) fraction of points ignored.
C2-2 Guilherme C. M. Gomes, Bruno P. Masquio, Paulo E. D. Pinto, Vinicius F. dos Santos and Jayme L. Szwarcfiter, Disconnected Matchings.
C2-3 Sun-Yuan Hsieh, Van Bang Le and Sheng-Lung Peng, On the d-Claw Vertex Deletion Problem.
C2-4 Ankush Acharyya, Vahideh Keikha, Diptapriyo Majumdar and Supantha Pandit, Constrained Hitting Set Problem with Intervals.
C2-5 Sen Huang, Mingyu Xiao and Xiaoyu Chen, Exact algorithms for maximum weighted independent set on sparse graphs.

2021.10.26 (Tue.)
09:00-09:30 Registration
09:30-10:00 A3-1 B3-1 C3-1
10:00-10:25 A3-2 B3-2 C3-2
10:25-10:50 A3-3 B3-3 C3-3
10:50-11:15 A3-4 B3-4 C3-4
11:15-11:40 A3-5 C3-5
11:40-13:00 Lunch
13:00-14:00 Keynote Speech #3 Prof. Tony Q.S. Quek
(Singapore University of Technology and Design, Singapore)
Session Chair: Prof. Sun-Yuan Hsieh
14:00-15:00 Keynote Speech #4 Prof. Ralf Klasing
(CNRS and University of Bordeaux, France)
Session Chair: Prof. Sun-Yuan Hsieh
15:00-15:15 Coffee/Tea Break
15:15-15:45 A4-1 B4-1 C4-1
15:45-16:10 A4-2 B4-2 C4-2
16:10-16:35 A4-3 B4-3 C4-3
16:35-17:00 A4-4 B4-4 C4-4
17:00-17:20 COCOON 2022
Session Chair: Prof. Sun-Yuan Hsieh

Session A3: Approximation Algorithms & Graph Algorithms
Session Chair: Jou-Ming Chang
A3-1 Arindam Biswas and Venkatesh Raman, Sublinear-Space Approximation Algorithms for Max r-SAT.
A3-2 Jingyang Zhao and Mingyu Xiao, A Further Improvement on Approximating TTP-2.
A3-3 Jan Goedgebeur, Shenwei Huang, Yiao Ju and Owen Merkel, Colouring graphs with no induced six-vertex path or diamond.
A3-4 Yu-Han Chen, Kung-Jui Pai, Hsin-Jung Lin and Jou-Ming Chang, Constructing Tri-CISTs in Shuffle-Cubes.
A3-5 Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi and Kunihiro Wasa, Reconfiguring Directed Trees in a Digraph.
Session B3: Graph Algorithms
Session Chair: Sheng-Lung Peng
B3-1 Yusuke Yanagisawa, Yuma Tamura, Akira Suzuki and Xiao Zhou, Decremental Optimization of Vertex-Coloring Under the Reconfiguration Framework.
B3-2 Kung-Jui Pai, Embedding Three Edge-disjoint Hamiltonian Cycles into Locally Twisted Cubes.
B3-3 Luerbio Faria and Uéverton Souza, On the Probe Problem for (r,l)-Well-Coveredness.
B3-4 Nina Klobas and Matjaž Krnc, Distinguishing graphs via cycles.
Session C3: Graph Theory and Applications
Session Chair: Chi-Yeh Chen
C3-1 Ruo-Wei Hung and Ming-Jung Chiu, The Restrained Domination and Independent Restrained Domination in Extending Supergrid Graphs.
C3-2 Alan Frieze, Krzysztof Turowski and Wojciech Szpankowski, The Concentration of the Maximum Degree in the Duplication-Divergence Models.
C3-3 Sambhav Gupta, Eddie Cheng and László Lipták, Conditional Fractional Matching Preclusion for Burnt Pancake Graphs and Pancake-Like Graphs.
C3-4 Justie Su-Tzu Juan and Zong-You Lai, The Weakly Dimension-balanced Pancyclicity on Toroidal Mesh Graph Tm,n when Both m and n Are Odd.
C3-5 Maciej Skorski, Hypercontractivity via Tensor Calculus.
Session A4: Fault Tolerant Computing and Fault Diagnosis
Session Chair: Chia-Wei Lee
A4-1 Yihong Wang, Shuming Zhou and Zhengqin Yu, Reliability Evaluation of Subsystem Based on Exchanged Hypercube.
A4-2 Jiafei Liu, Shuming Zhou, Qianru Zhou and Zhengqin Yu, Fault diagnosability of regular networks under the Hybrid PMC model.
A4-3 Nai-Wen Chang, Hsuan-Jung Wu and Sun-Yuan Hsieh, A Study for Conditional Diagnosability of Pancake Graphs.
A4-4 Meirun Chen, D. Frank Hsu and Cheng-Kuan Lin, A new measure for locally t-diagnosable under PMC model.
Session B4: Network and Algorithms
Session Chair: Ling-Ju Hung
B4-1 Neelima Gupta, Sapna Grover and Rajni Dabas, Respecting Lower Bounds in Uniform Lower and Upper Bounded Facility Location Problem.
B4-2 Wei Ding, Finding Cheapest Deadline Paths.
B4-3 Lu Han, Chenchen Wu and Yicheng Xu, Approximate the Lower-Bounded Connected Facility Location Problem.
B4-4 Longteng Duan, Zifan Gong, Minming Li, Chenhao Wang and Xiaoying Wu, Mechanism Design for Facility Location with Fractional Preferences and Minimum Distance.
Session C4: Automata
Session Chair: Tomoyuki Yamakami
C4-1 Tomoyuki Yamakami, Between SC and LOGDCFL: Families of Languages Accepted by Polynomial-Time Logarithmic-Space Deterministic Auxiliary Depth-k Storage Automata.
C4-2 Sammy Khalife, Yann Ponty and Laurent Bulteau, Sequence graphs realizations and ambiguity in language models.
C4-3 Stefan Hoffmann, Ideal Separation and General Theorems for Constrained Synchronization and their Application to Small Constraint Automata.
C4-4 Hyunjoon Cheon, Joonghyuk Hahn, Yo-Sub Han and Sang-Ki Ko, Most Pseudo-copy Languages Are Not Context-free.