|
Program
COCOON 2013 will be held at Yuquan Campus, Zhejiang University. The conference venue is Run Run Shaw Science Building.
June 20
| Time |
Venue |
Events |
| 15:00--21:00 |
Lily Hotel |
On-site registration |
NOTE:From June 21, there is also on-site registration from 8:00am at Run Run Shaw Science Building.
June 21
| Time |
Venue |
Events |
Chairs |
| 8:30--8:40 |
117 |
Opening |
| 8:40--9:40 |
117 |
Recent Results for Online Makespan Minimization(Invited Talk)
Susanne Albers |
Guochuan Zhang |
| 9:40--10:10 |
|
Photo & Coffee break |
| 10:10--11:50 |
117 |
Game Theory |
Minming Li |
New Bounds for the Balloon Popping Problem
Vittorio Bilò, Davide Bilò |
On the Sequential Price of Anarchy of Isolation Games
Anna Angelucci,Vittorio Bilò, Michele Flammini, Luca Moscardelli
|
Social Exchange Networks with Distant Bargaining
Konstantinos Georgiou, George Karakostas, Jochen Konemann,
Zuzanna Stamirowska |
The 1/4-Core of the Uniform Bin Packing Game is Nonempty
Xian Qiu,Walter Kern |
| 211-212 |
Randomized Algorithms |
Bernard Mans |
On the Advice Complexity of the Online L(2,1)-coloring Problem
on Paths and Cycles
Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovic,
Sacha Krug, Björn Steffen |
A Fast Algorithm for Data Collection along a Fixed Track
Otfried Cheong, Radwa El Shawi, Joachim Gudmundsson
|
Random Methods for Parameterized Problems
Qilong Feng, Jianxin Wang, Shaohua Li, Jianer Chen |
| 11:50-13:30 |
|
Lunch |
| 13:30--15:10 |
211 |
Scheduling Algorithms |
Donglei Du |
DVS Scheduling in a Line or a Star Network of Processors
Zongxu Mu, Minming Li
|
Online Algorithms For Batch Machines Scheduling with Delivery Times
Peihai Liu, Xiwen Lu |
How to Schedule the Marketing of Products with Negative Externalities
Zhigang Cao, Xujin Chen, Changjun Wang
|
From Preemptive to Non-preemptive Speed-Scaling Scheduling
Evripidis Bampis, Alexander Kononov, Dimitrios Letsios,
Giorgio Lucarelli, Ioannis Nemparis
|
| 212 |
Computational Theory |
Joachim Gudmundsson |
Selection from Read-Only Memory with Limited Workspace
Amr Elmasry, Daniel Dahl Juhl, Jyrki Katajainen, Srinivasa Rao Satti
|
Determinization of Büchi Automata by Partitioned Automata
Cong Tian
|
On Linear-Size Pseudorandom Generators and Hardcore Functions
Joshua Baron, Yuval Ishai, Rafail Ostrovsky
|
A Fast Algorithm Finding the Shortest Reset Words
Andrzej Kisielewicz, Jakub Kowalski, Marek Szykuła
|
| 15:10--15:30 |
|
Coffee break |
| 15:30--17:10 |
211 |
Computational Geometry |
Binhai Zhu |
The Discrete Voronoi Game in a Simple Polygon
Aritra Banik, Sandip Das, Anil Maheshwari, Michiel Smid
|
Facets for Art Gallery Problems
Sándor Fekete, Stephan Friedrichs, Alexander Kröller,Christiane Schmidt
|
Hitting and Piercing Rectangles Induced by a Point Set
Ninad Rajgopal, Pradeesha Ashok, Sathish Govindarajan,
Abhijit Khopkar, Neeldhara Misra
|
Realistic Roofs over a Rectilinear Polygon Revisited
Jessica Sherette, Sang Duk Yoon
|
| 212 |
Graph Algorithms I |
Lusheng Wang |
Parametric Power Supply Network
Shiho Morishita, Takao Nishizeki
|
Approximating the Minimum Independent Dominating Set in Perturbed Graphs
Weitian Tong, Randy Goebel, Guohui Lin
|
A Linear-Time Algorithm for the Minimum Degree Hypergraph Problem with the Consecutive Ones Property
Chih-Hsuan Li, Jhih-Hong Ye, Biing-Feng Wang
|
On the Conjunctive Capacity of Graphs
Janka Chlebikova, Miroslav Chlebik
|
June 22
| Time |
Venue |
Events |
Chairs |
| 8:30--10:10 |
211 |
Approximation Algorithms |
Xiaodong Hu |
Improved Approximation Algorithms for the Facility Location Problems with Linear/Submodular Penalty
Yu Li, Donglei Du, Naihua Xiu, Dachuan Xu
|
An Improved Semidefinite Programming Hierarchies Rounding Approximation Algorithm for Maximum Graph Bisection Problems
Chenchen Wu, Donglei Du, Dachuan Xu
|
Improved Local Search for Universal Facility Location
Eric Angel, Kim Thang Nguyen, Damien Regnault |
Improved Approximation Algorithms for Computing k Disjoint Paths Subject to Two Constraints
Longkun Guo, Kewen Liao, Hong Shen
|
| 212 |
Graph Algorithms Ⅱ |
Janka Chlebikova |
The k-Separator Problem
Walid Ben-Ameur, Mohamed-Ahmed Mohamed-Sidi, Jose Neto
|
On the Treewidth of Dynamic Graphs
Bernard Mans, Luke Mathieson
|
Square-Orthogonal Drawing with Few Bends per Edge
Yu-An Lin, Sheung-Hung Poon
|
Covering Tree with Stars
Rashid Ibragimov, Jiong Guo, Jan Baumbach
|
| 203 |
CSoNet I |
Ding-Zhu Du |
A New Model for Product Adoption over Social Networks
Lidan Fan, Zaixin Lu, Weili Wu, Yuanjun Bi, Ailian Wang
|
Generating Uncertain Networks based on Historical Network Snapshots
Meng Han, Mingyuan Yan, Jinbao Li, Shouling Ji, Yingshu Li
|
A Short-term Prediction Model of Topic Popularity on Microblogs
Juanjuan Zhao, Weili Wu, Xiaolong Zhang, Yan Qiang, Tao Liu, Lidong Wu
|
Social Network Path Analysis based on HBase
Yan Qiang, Junzuo Lu, Weili Wu, Juanjuan Zhao, Xiaolong Zhang, Yue Li, Lidong Wu
|
| 10:10--10:25 |
|
Coffee break |
| 10:25--12:05 |
211 |
Computational Biology |
Guohui Lin |
A Polynomial Time Approximation Scheme for the Closest Shared Center Problem
Weidong Li, Lusheng Wang, Wenjuan Cui
|
An Improved Approximation Algorithm for Scaffold Filling to Maximize the Common Adjacencies
Nan Liu, Haitao Jiang, Daming Zhu, Binhai Zhu
|
An Efficient Algorithm for One-Sided Block Ordering Problem with Block-Interchange Distance
Kun-Tze Chen, Chi-Long Li, Chung-Han Yang, Chin Lung Lu
|
A Combinatorial Approach for Multiple RNA Interaction: Formulations, Approximations, and Heuristics
Syed Ali Ahmed, Saad Mneimneh, Nancy L. Greenbaum
|
| 212 |
Graph Algorithms Ⅲ |
George Karakostas |
Maximum Balanced Subgraph Problem Parameterized Above Lower Bound
Robert Crowston, Gregory Gutin, Mark Jones, Gabriele Muciaccia
|
A Toolbox for Provably Optimal Multistage Strict Group Testing Strategies
Peter Damaschke, Azam Sheikh Muhammad
|
A Linear Edge Kernel for Two-Layer Crossing Minimization
Yasuaki Kobayashi, Hirokazu Maruta, Yusuke Nakae, Hisao Tamaki
|
A Linear-Time Algorithm for Computing the Prime Decomposition of a Directed Graph with Regard to the Cartesian Product
Christophe Crespelle Eric Thierry, Thomas Lambert
|
| 203 |
CSoNet Ⅱ |
Ronaldo Menezes |
Community Expansion Model Based on Charged System Theory
Yuanjun Bi, Weili Wu, Ailian Wang, Lidan Fan
|
Centrality and Spectral Radius in Dynamic Communication Networks
Danica Vukadinovic Greetham, Zhivko Stoyanov, Peter Grindrod
|
Finding Network Communities using Random Walkers with Improved Accuracy
You Li, Jie Wang, Benyuan Liu, Qilian Liang
|
Homophilies and Communities Detection Among A Subset of Blogfa Persian Weblogs:Computer and Internet Category
Adib Rastegarnia, Meysam Mohajer, Vahid Solouk
|
| 12:05--13:30 |
|
Lunch |
| 13:30--15:10 |
211 |
Online Algorithms |
Walter Kern |
Metrical Service Systems with Multiple Servers
Ashish Chiplunkar, Sundar Vishwanathan
|
The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity
Hans-Joachim B?ckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula, Andreas Sprock
|
Online Algorithms for 1-Space Bounded 2-Dimensional Bin Packing and Square Packing
Yong Zhang, Francis Y.L. Chin, Hingfung Ting, Xin Han, Chung Keung Poon, Yung H. Tsin, Deshi Ye
|
Improved Lower Bounds for the Online Bin Packing Problem with Cardinality Constraints
Hiroshi Fujiwara, Koji Kobayashi
|
| 212 |
Workshop I |
Tian Liu |
Straight-Line Monotone Grid Drawings of Series-Parallel Graphs
Md. Iqbal Hossain, Md Saidur Rahman
|
Combination of Two-machine Flow Shop Scheduling and Shortest Path Problems
Kameng Nip, Zhenbo Wang
|
The Program Download Problem: Complexity and Algorithms
Chao Peng, Jie Zhou, Binhai Zhu, Hong Zhu
|
Finding Theorems in NBG Set Theory by Automated Forward Deduction Based on Strong Relevant Logic
Hongbiao Gao, Kai Shi, Yuichi Goto, Jingde Cheng
|
| 203 |
CSoNet Ⅲ |
Jinbao Li |
Neighborhood-based Dynamic Community Detection with Graph Transform for 0-1 Observed Networks
Li Wang, Weili Wu, Yuanjun Bi, Wen Xu, Biao Lian
|
Effects of Inoculation based on Structural Centrality on Rumor Dynamics in Social Networks
Anurag Singh, Rahul Kumar, and Yatindra Nath Singh
|
A Dominating Set Based Approach to Identify Effective Leader Group of Social Network
Donghyun Kim, Deying Li, Omid Asgari, Yingshu Li, and Alade O. Tokuta
|
Using Network Sciences to Evaluate the Brazilian Airline Network
Douglas Oliveira, Marco Carvalho, Ronaldo Menezes
|
| 15:10--15:30 |
|
Coffee break |
| 15:30--17:10 |
211 |
Parameterized Algorithms |
Evripidis Bampis |
Parameterized Complexity of Flood-Filling Games on Trees
Ueverton Souza, Fábio Protti, Maise Dantas da Silva
|
Parameterized Approximability of Influence in Social Networks
Cristina Bazgan, Morgan Chopin, André Nichterlein, Florian Sikora
|
An Effective Branching Strategy for Some Parameterized Edge Modification Problems with Multiple Forbidden Induced Subgraphs
Yunlong Liu, Jianxin Wang, Jiong Guo, Jianer Chen, Chao Xu
|
Parameterized Algorithms for Maximum Agreement Forest on Multiple Trees
Feng Shi, Jianer Chen, Qilong Feng, Jianxin Wang |
| 203 |
Workshop Ⅱ |
Hong Zhu |
Perturbation Analysis of Maximum-Weighted Bipartite Matchings with Low Rank Data
Xingwu Liu, Shang-Hua Teng
|
Sublinear Time Approximate Sum via Uniform Random Sampling
Bin Fu, Wenfeng Li, Zhiyong Peng
|
Tractable Connected Domination for Restricted Bipartite Graphs
Zhao Lu, Tian Liu, Ke Xu
|
On the Minimum Caterpillar Problem in Digraphs
Taku Okada, Akira Suzuki, Takehiro Ito, Xiao Zhou
|
| 18:00--20:00 |
|
Banquet(at the restaurant of Run Run Shaw Science Building) |
June 23
| Time |
Venue |
Events |
Chairs |
| 8:30--9:30 |
211-212
|
Optimal Stopping Meets Combinatorial Optimization(Invited Talk)
Robert Kleinberg
|
Ding-Zhu Du |
| 9:30--9:50 |
|
Coffee break |
| 9:50--11:30 |
211 |
Computational Complexity |
Francis Chin |
Small H-coloring problems for bounded degree digraphs
Aurosish Mishra, Pavol Hell
|
Bounded Model Checking for Propositional Projection Temporal Logic
Zhenhua Duan
|
Packing Cubes into a Cube is NP-hard in the Strong Sense
Yiping Lu, Danny Chen, Jianzhong Cha
|
| 212 |
Algorithms |
Yung H. Tsin |
2-connecting Outerplanar Graphs without Blowing Up the Pathwidth
Jasine Babu, Manu Basavaraju, L.Sunil Chandran, Deepak Rajendraprasad |
How to Catch L2-Heavy-Hitters on Sliding Windows
Vladimir Braverman, Ran Gelles, Rafail Ostrovsky
|
Time/Memory/Data Tradeoffs for variants of the RSA Problem
Pierre-Alain Fouque, Damien Vergnaud, Jean-Christophe Zapalowicz
|
An Improved Algorithm for Extraction of Exact Boundaries and Boundaries Inclusion Relationship
Tao Hu, Xinyi Ren, Jihong Zhang
|
| 11:30--13:00 |
|
Lunch(at the restaurant of Lily Hotel) |
| 13:30--20:30 |
|
Local Tour |
|
|
