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 | |
B2-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
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. (Best Paper) |
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. Ling-Ju Hung |
||
14:00-15:00 |
Keynote Speech #4 Prof. Ralf Klasing (CNRS and University of Bordeaux, France) Session Chair: Prof. Ling-Ju Hung |
||
15:00-15:05 | Best Paper Award Ceremony Session Chair: Prof. Ralf Klasing |
||
15:05-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. Ling-Ju Hung |
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. |