Accepted Papers

Main Conference Papers:

• Shiho Morishita and Takao Nishizeki
  002 Parametric power supply network


• Ueverton Souza, Fábio Protti and Maise Dantas da Silva
  003 Parameterized complexity of flood-filling games on trees


• Andrzej Kisielewicz, Jakub Kowalski and Marek Szykuła
  009 A fast algorithm finding the shortest reset words


• Peihai Liu and Xiwen Lu
  011 Online algorithms for batch machines scheduling with delivery times


• Yu Li, Donglei Du, Naihua Xiu and Dachuan Xu
  014 Improved approximation algorithms for the facility location problems with linear/submodular penalty


• Chenchen Wu, Donglei Du and Dachuan Xu
  016 An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems


• Weitian Tong, Randy Goebel and Guohui Lin
  017 Approximating the minimum independent dominating set in perturbed graphs


• Robert Crowston, Gregory Gutin, Mark Jones and Gabriele Muciaccia
  021 Maximum balanced subgraph problem parameterized above lower bound


• Walid Ben-Ameur, Mohamed-Ahmed Mohamed-Sidi and Jose Neto
  026 The k-separator problem


• Jasine Babu, Manu Basavaraju, L. Sunil Chandran and Deepak Rajendraprasad
  029 2-connecting outerplanar graphs without blowing up the pathwidth


• Manoel Campêlo, Cristiana Huiban, Rudini Sampaio and Yoshiko Wakabayashi
  034 On the complexity of solving or approximating convex recoloring problems


• Zongxu Mu and Minming Li
  035 DVS scheduling in a line or a star network of processors


• Ashish Chiplunkar and Sundar Vishwanathan
  036 Metrical service systems with multiple servers


• Bernard Mans and Luke Mathieson
  038 On the treewidth of dynamic graphs


• Hans-Joachim Böckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula and Andreas Sprock
  044 The string guessing problem as a method to prove lower bounds on the advice complexity


• Vladimir Braverman, Ran Gelles and Rafail Ostrovsky
  045 How to catch l2-heavy-hitters on sliding windows


• Peter Damaschke and Azam Sheikh Muhammad
  047 A toolbox for provably optimal multistage strict group testing strategies


• Chih-Hsuan Li, Jhih-Hong Ye and Biing-Feng Wang
  048 A linear-time algorithm for the minimum degree hypergraph problem with the consecutive ones property


• Pierre-Alain Fouque, Damien Vergnaud and Jean-Christophe Zapalowicz
  050 Time/memory/data tradeoffs for variants of the RSA problem


• Aritra Banik, Sandip Das, Anil Maheshwari and Michiel Smid
  052 The discrete voronoi game in a simple polygon


• Sándor Fekete, Stephan Friedrichs, Alexander Kröller and Christiane Schmidt
  053 Facets for art gallery problems


• Maria Paola Bianchi, Hans-Joachim Böckenhauer, Juraj Hromkovic, Sacha Krug and Björn Steffen
  055 On the advice complexity of the online L(2,1)-coloring problem on paths and cycles


• Khaled Elbassioni, Kazuhisa Makino, Kurt Mehlhorn and Fahimeh Ramezani
  056 On randomized fictitious play for approximating saddle points over convex sets


• Cristina Bazgan, Morgan Chopin, AndréNichterlein and Florian Sikora
  057 Parameterized approximability of influence in social networks


• Otfried Cheong, Radwa El Shawi and Joachim Gudmundsson
  065 A fast algorithm for data collection along a fixed track


• Weidong Li, Lusheng Wang and Wenjuan Cui
  066 A polynomial time approximation scheme for the closest shared center problem


• Zhigang Cao, Xujin Chen and Changjun Wang
  067 How to schedule the marketing of products with negative externalities


• Yu-An Lin and Sheung-Hung Poon
  069 Square-orthogonal drawing with few bends per edge


• Janka Chlebikova and Miroslav Chlebik
  070 On the conjunctive capacity of graphs


• Rashid Ibragimov, Jiong Guo and Jan Baumbach
  071 Covering tree with stars


• Vittorio Bilò and Davide Bilò
  072 New bounds for the balloon popping problem


• Anna Angelucci, Vittorio Bilò, Michele Flammini and Luca Moscardelli
  074 On the sequential price of anarchy of isolation games


• Konstantinos Georgiou, George Karakostas, Jochen Konemann and Zuzanna Stamirowska
  076 Social exchange networks with distant bargaining


• Nan Liu, Haitao Jiang, Daming Zhu and Binhai Zhu
  077 An improved approximation algorithm for scaffold filling to maximize the common adjacencies


• Aurosish Mishra and Pavol Hell
  084 Small H-coloring problems for bounded degree digraphs


• Xian Qiu and Walter Kern
  087 Mind the (relative) gap for bin packing games


• Kun-Tze Chen, Chi-Long Li, Chung-Han Yang and Chin Lung Lu
  090 An efficient algorithm for one-sided block ordering problem with block-interchange distance


• Eric Angel, Kim Thang Nguyen and Damien Regnault
  092 Improved local search for universal facility location


• Ninad Rajgopal, Pradeesha Ashok, Sathish Govindarajan, Abhijit Khopkar and Neeldhara Misra
  094 Hitting and piercing rectangles induced by a point set


• Tao Hu, Xinyi Ren and Jihong Zhang
  097 An improved algorithm for extraction of exact boundaries and boundaries inclusion relationship


• Zhenhua Duan
  100 Bounded model checking for propositional projection temporal logic


• Yong Zhang, Francis Y.L. Chin, Hingfung Ting, Xin Han, Chung Keung Poon, Yung H. Tsin and Deshi Ye
  101 Online algorithms for 1-space bounded 2-dimensional bin packing and square packing


• Longkun Guo, Kewen Liao and Hong Shen
  102 Improved approximation algorithms for computing k disjoint paths subject to two constraints


• Amr Elmasry, Daniel Dahl Juhl, Jyrki Katajainen and Srinivasa Rao Satti
  103 Selection from read-only memory with limited workspace


• Cong Tian
  105 Determinization of Büchi automata by partitioned automata


• Syed Ali Ahmed, Saad Mneimneh and Nancy L. Greenbaum
  110 A combinatorial approach for multiple RNA interaction: formulations, approximations, and heuristics


• Yunlong Liu, Jianxin Wang, Jiong Guo, Jianer Chen and Chao Xu
  112 An effective branching strategy for some parameterized edge modification problems with multiple forbidden induced subgraphs


• Joshua Baron, Yuval Ishai and Rafail Ostrovsky
  113 On linear-size pseudorandom generators and hardcore functions


• Evripidis Bampis, Alexander Kononov, Dimitrios Letsios, Giorgio Lucarelli and Ioannis Nemparis
  115 From preemptive to non-preemptive speed-scaling scheduling


• Jessica Sherette and Sang Duk Yoon
  118 Realistic roofs over a rectilinear polygon revisited


• Yiping Lu, Danny Chen and Jianzhong Cha
  120 Packing cubes into a cube is NP-hard in the strong sense


• Feng Shi, Jianer Chen, Qilong Feng and Jianxin Wang
  121 Parameterized algorithms for maximum agreement forest on multiple trees


• Qilong Feng, Jianxin Wang, Shaohua Li and Jianer Chen
  122 Random methods for parameterized problems


• Yasuaki Kobayashi, Hirokazu Maruta, Yusuke Nakae and Hisao Tamaki
  125 A linear edge kernel for two-layer crossing minimization


• Hiroshi Fujiwara and Koji Kobayashi
  126 Improved lower bounds for the online bin packing problem with cardinality constraints


• Christophe Crespelle, Eric Thierry and Thomas Lambert
  128 A linear-time algorithm for computing the prime decomposition of a directed graph with regard to the cartesian product

Workshop Papers:

• Md. Iqbal Hossain and Md Saidur Rahman
  027 Straight-line monotone grid drawings of series-parallel graphs


• Kameng Nip and Zhenbo Wang
  042 Combination of two-machine flow shop scheduling and shortest path problems


• Chao Peng, Jie Zhou, Binhai Zhu and Hong Zhu
  078 The program download problem: complexity and algorithms


• Hongbiao Gao, Kai Shi, Yuichi Goto and Jingde Cheng
  085 Finding theorems in NBG set theory by automated forward deduction based on strong relevant logic


• Xingwu Liu and Shang-Hua Teng
  093 Perturbation analysis of maximum-weighted bipartite matchings with low rank data


• Bin Fu, Wenfeng Li and Zhiyong Peng
  109 Sublinear time approximate sum via uniform random sampling


• Zhao Lu, Tian Liu and Ke Xu
  114 Tractability of connected domination for circular- and triad-convex bipartite graphs


• Taku Okada, Akira Suzuki, Takehiro Ito and Xiao Zhou
  123 On the minimum caterpillar problem in digraphs