COCOON 2020

Opening and Invited Talk

9:00 - 9:10

Opening
Prof. R.N. Uma and Prof. Donghyun Kim (TPC co-Chairs)

9:10 - 10:00

Keynote 1
Prof. Zhi Tian (Host: Prof. Donghyun Kim)

10:00 - 10:10

Break

10:10 - 11:00

Keynote 2
Prof. Junshan Zhang (Host: Prof. Zhipeng Cai)

11:00 - 11:30

Virtual Coffee Break

11:30 - 13:00

Virtual Lunch Break

Session 1 (Chair: Dr. Peng Zhang)

13:00 - 13:20

Flavia Bonomo-Braberman, Julliano Nascimento, Fabiano Oliveira, Uéverton Souza and Jayme Szwarcfiter
Linear-time Algorithms for Eliminating Claws in Graphs

13:20 - 13:40

Jasine Babu and Veena Prabhakaran
A new lower bound for the eternal vertex cover number of graphs

13:40 - 14:00

Jan Gorzny and Jing Huang  
End-Vertices of AT-free Bigraphs

14:00 - 14:20

Nicolas Grelier          
Computing a Maximum Clique in Geometric Superclasses of Disk Graphs

14:20 - 14:40

Kathie Cameron, Jan Goedgebeur, Shenwei Huang and Yongtang Shi
$k$-Critical Graphs in $P_5$-Free Graphs

14:40 - 15:00

Virtual Coffee Break

Session 2 (Chair: Dr. Anirban Ghosh)

15:00 - 15:20

Johannes Blum           
W[1]-Hardness of the k-Center Problem Parameterized by the Skeleton Dimension

15:20 - 15:40

Bin Fu
Hardness of Sparse Sets and Minimal Circuit Size Problem 

15:40 - 16:00

Andrea Caucchiolo and Ferdinando Cicalese
On the complexity of directed intersection representation of DAGs

16:00 - 16:20

Manuel Lafond           
Even better fixed-parameter algorithms for bicluster editing

16:20 - 16:40

Bin Fu, Pengfei Gu and Yuming Zhao          
Approximate Set Union via Approximate Randomization

Session 3 (Chair: Dr. Xiaoming Sun)

8:10 - 8:30

Zhi Cao and Nan Zhang        
Deep Specification Mining with Attention   

8:30 - 8:50

Prashanth Amireddy, Sai Jayasurya and Jayalal Sarma      
Power of Decision Trees with Monotone Queries     

8:50 - 9:10

Mateus Alves, Mateus De Oliveira Oliveira, Janio Silva and Uéverton Souza          
Succinct Monotone Circuit Certification: Planarity and Parameterized Complexity

9:10 - 9:30

Prashanth Amireddy, Sai Jayasurya and Jayalal Sarma      
On the Mystery of Negations in Circuits : Structure vs Power

9:30 - 9:50

Virtual Coffee Break

Session 4 (Chair: Dr. Jayalal Sarma)

9:50 - 10:10

Amit Deshpande and Rameshwar Pratap
Subspace approximation with outliers
Best Paper Award Winner

10:10 - 10:30

Rémi Géraud-Stewart, Marius Lombard-Platet and David Naccach       
Approaching Optimal Duplicate Detection in a Sliding Window    

10:30 - 10:50

Mohammad Abouei Mehrizi, Federico Corò, Emilio Cruciani and Gianlorenzo D'Angelo           
Election Control through Social Influence with Unknown Preferences     

10:50 - 11:10

Om Prakash and Raghavendra Rao B V       
On Measures of Space Over Real and Complex numbers     

11:10 - 11:30

Hongxiang Zhang, Dachuan Xu, Longkun Guo and Jingjing Tan    
Parallelized maximization of nonsubmodular function subject to a cardinality constraint 

11:30 - 11:50

Umang Bhaskar and Gunjan Kumar 
A Non-Extendibility Certificate for Submodularity and Applications   

12:00 - 14:00

Virtual Lunch Break

Session 5 (Chair: Dr. Joon-Lyul Lee)

14:00 - 14:20

Christian Deppe, Vladimir Lebedev, Georg Maringer and Nikita Polianskii       
Coding with Noiseless Feedback over the Z-channel

14:20 - 14:40

Vipin Singh Sehrawat and Yvo Desmedt       
Access Structure Hiding Secret Sharing from Novel Set Systems and Vector Families

14:40 - 15:00

Matthew Dippel, Ravi Sundaram and Akshar Varma
Realization Problems on Reachability Sequences

15:00 - 15:20

Gregory Gutin, Philip Neary and Anders Yeo
Uniqueness of $DP$-Nash Subgraphs and $D$-sets

15:20 - 15:40

Nai-Wen Chang and Sun-Yuan Hsieh
A Survey for Conditional Diagnosability of Alternating Group Networks

15:40 - 16:00

Ivona Bezakova and Wenbo Sun        
Mixing of Markov Chains for Independent Sets on Chordal Graphs with Bounded Separators

16:00 - 16:20

Virtual Lunch Break

Session 6 (Chair: Dr. Nikita Polianskii)

16:20 - 16:40

Jie-Fu Huang and Sun-Yuan Hsieh   
Constructing Independent Spanning Trees in Alternating Group Networks

16:40 - 17:00

Masayuki Miyamoto, Masakazu Iwamura, Koichi Kise and François Le Gall
Quantum Speedup for the Minimum Steiner Tree Problem

17:00 - 17:20

Yuichi Asahiro, Eto, Tesshu Hanaka, Guohui Lin, Eiji Miyano and Ippei Terabaru   
Graph Classes and Approximability of the Happy Set Problem

17:20 - 17:40

Prosenjit Bose, Anthony D'Angelo and Stephane Durocher 
On the Restricted 1-Steiner Tree Problem
Best Paper Runner Up Award Winner

17:40 - 18:00

Xiaoyun Tian, Dachuan Xu, Longkun Guo and Dan Wu      
An improved Bregman $k$-means++ algorithm via local search

18:00 - 18:20

Lu Han, Chunlin Hao, Chenchen Wu and Zhenning Zhang 
Approximation algorithms for the lower-bounded k-median and its generalizations

Session 7 (Chair: Dr. Martin Ziegler)

8:10 - 8:30

Seok-Hee Hong and Hiroshi Nagamochi      
Path-monotonic Upward Drawings of Plane Graphs

8:30 - 8:50

Sanjana Agrawal and R. Inkulu         
Visibility polygon queries among dynamic polygonal obstacles in plane

8:50 - 9:10

Bengt J. Nilsson, David Orden, Leonidas Palios, Carlos Seara and Paweł Żyliński
Shortest Watchman Tours in Simple Polygons under Rotated Monotone Visibility

9:10 - 9:30

Giordano Da Lozzo, D'Angeloand Fabrizio Frati 
On the Area Requirements of Planar Greedy Drawings of Triconnected Planar Graphs

9:30 - 9:50

Virtual Coffee Break

Session 8 (Chair: Dr. R. Inkulu)

9:50 - 10:10

André van Renssen and Gladys Wong           
Bounded-Degree Spanners in the Presence of Polygonal Obstacles 
Best Paper Runner Up Award Winner

10:10 - 10:30

Stefan Funke  
Seamless Interpolation between Contraction Hierarchies and Hub Labels for fast and space-efficient Shortest Path Queries in Road Networks

10:30 - 10:50

Milutin Brankovic, André van Renssen and Joachim Gudmundsson
Local Routing in a Tree Metric 1-Spanner

10:50 - 11:10

Patrick Eades and Julian Mestre       
An Optimal Lower Bound for Hierarchical Universal Solutions for TSP on the Plane

11:10 - 11:30

Hans L. Bodlaender, Josse van Dobben de Bruyn, Dion Gijswijt and Harry           
Constructing Tree Decompositions of Graphs with Bounded Gonality

11:30 - 11:50

Xiaoyan Zhang, Donglei Du, Gutin, Qiaoxia Ming and Jian Sun         
Approximation algorithms for cluster general routing problem

12:00 - 14:00

Virtual Lunch Break

Session 9 (Chair: Dr. Yan Huang)

14:00 - 14:20

Kelin Luo and Frits Spieksma
Approximation algorithms for car-sharing problems

14:20 - 14:40

Julian Mestre and Nicolas Stier Moses         
Tight approximation for the minimum bottleneck generalized matching problem

14:40 - 15:00

Stephan Beyer, Markus Chimani and Joachim Spoerhase    
A Simple Primal-Dual Approximation Algorithm for 2-Edge-Connected Spanning Subgraphs

15:00 - 15:20

Naveed Ahmed Azam, Aleksandar Shurbevski and Hiroshi Nagamochi
On the Enumeration of Minimal Non-Pairwise Compatibility Graphs

15:20 - 15:40

Khadija Hadj Salem and Yann Kieffer          
New Symmetry-less ILP Formulation for the Classical One Dimensional Bin-Packing Problem

15:40 - 16:00

Julien Baste, Maximilian Fürst and Dieter Rautenbach       
Approximating Maximum Acyclic Matchings by Greedy and Local Search Strategies

16:00 - 16:20

Virtual Lunch Break

Session 10 (Chair: Dr. R.N. Uma)

16:20 - 16:40

Lin Chen, Ahmed Sunny, Lei Xu, Shouhuai Xu, Zhimin Gao, Nolan Shah, Yang Lu and Weidong Shi
Computational Complexity Characterization of Protecting Elections from Bribery          

16:40 - 17:00

Xianmin Liu, Jianzhong Li and Yingshu Li   
On the Parameterized Complexity of Completeness Reasoning for Conjunctive Queries

17:00 - 17:20

Neeldhara Misra and Harshil Mittal 
Imbalance Parameterized by Twin Cover Revisited

17:20 - 17:40

Stefan Hoffmann        
Computational Complexity of Synchronization under Regular Commutative Constraints

17:40 - 18:00

Akanksha Agrawal, Madhumita Kundu, Abhishek Sahu, Saket Saurabh and Prafullkumar Tale        
Parameterized Complexity of Maximum Edge Colorable Subgraph

18:00 - 18:20

Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra and Saket Saurabh
Fixed Parameter Tractability of Graph Deletion Problems over Data Streams