Accepted Papers - Regular Papers

  1. Finding Strong Bridges and Strong Articulation Points in Linear Time
    Giuseppe F. Italiano, Luigi Laura, and Federico Santaroni

  2. Searching for An Axis-Parallel Shoreline
    Elmar Langetepe

  3. The Union of Colorful Simplices Spanned by A Colored Point Set
    André Schulz and Csaba Toth

  4. Compact Visibility Representation of 4-Connected Plane Graphs
    Xin He, Jiun-Jie Wang, and Huaming Zhang

  5. Approximate Ellipsoid in The Streaming Model
    Asish Mukhopadhyay, Animesh Sarker, and Tom Switzer

  6. Coverage with k-Transmitters in The Presence of Obstacles
    Brad Ballinger, Nadia Benbernou, Prosenjit Bose, Mirela Damian, Erik D. Demaine, Vida Dujmovic, Robin Flatland, Ferran Hurtado, John Iacono, Anna Lubiw, Pat Morin, Vera Sacristan, Diane Souvaine, and Ryuhei Uehara

  7. Diameter-Constrained Steiner Tree
    Wei Ding, Guohui Lin, and Guoliang Xue

  8. Discrete Optimization with Polynomially Detectable Boundaries and Restricted Level Sets
    Yakov Zinder, Julia Memar, and Gaurav Singh

  9. Robust Optimization of Graph Partitioning and Critical Node Detection in Analyzing Networks
    Neng Fan and Panos M. Pardalos

  10. Some Variations on Constrained Minimum Enclosing Circle Problem
    Arindam Karmakar, Sandip Das, Subhas C. Nandy, and Binay Bhattacharya

  11. Extended Dynamic Subgraph Statistics Using h-Index Parameterized Data Structures
    David Eppstein, Michael T. Goodrich, Darren Strash, and Lowell Trott

  12. PTAS for Minimum Connected Dominating Set with Routing Cost Constraint in Wireless Sensor Networks
    Hongwei Du, Qiang Ye, Jiaofei Zhong, Amy Wang, Wonjun Lee, and Haesun Park

  13. An Efficient Algorithm For Chinese Postman Walk on Bi-Directed de Bruijn Graphs
    Vamsi Kundeti, Sanguthevar Rajasekaran, and Heiu Dinh

  14. On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs
    Yilin Shen, Dung T. Nguyen, and My T. Thai

  15. On Symbolic OBDD-Based Algorithms for The Minimum Spanning Tree Problem
    Beate Bollig

  16. Reducing The Maximum Latency of Selfish Ring Routing via Pairwise Cooperations
    Xujin Chen, Xiaodong Hu, and Weidong Ma

  17. A Primal-Dual Approximation Algorithm for The Asymmetric Prize-Collecting TSP
    Viet Hung Nguyen

  18. Computing Toolpaths for 5-Axis NC Machines
    Danny Z. Chen and Ewa Misiolek

  19. Transporting Jobs Through a Processing Center with Two Parallel Machines
    Hans Kellerer, Alan J. Soper, and Vitaly A. Strusevich

  20. Scheduling Packets with Values and Deadlines in Size-Bounded Buffers
    Fei Li

  21. A Trichotomy Theorem for The Approximate Counting of Complex-Weighted Bounded-Degree Boolean CSPs
    Tomoyuki Yamakami

  22. The Networked Common Goods Game
    Jinsong Tan

  23. Cyclic Vertex Connectivity of Star Graphs
    Zhihua Yu, Qinghai Liu, and Zhao Zhang

  24. The Number of Shortest Paths in The (n, k)-Star Graphs
    Eddie Cheng, Ke Qiu, and Zhi Zhang Shen

  25. An Improved Approximation Algorithm for Spanning Star Forest in Dense Graphs
    Jing He and Hongyu Liang

  26. Randomized Algorithms for Weighted Approximation of Points by a Step Function
    Jin-Yi Liu

  27. Approximating Multilinear Monomial Coefficients and Maximum Multilinear Monomials in Multivariate Polynomials
    Zhixiang Chen and Bin Fu

  28. Construction of Mixed Covering Arrays of Variable Strength Using a Tabu Search Approach
    Loreto Gonzalez-Hernandez, Nelson Rangel-Valdez, and Jose Torres-Jimenez

  29. Complexity of Determining The Most Vital Elements for The 1-Median and 1-Center Location Problems
    Cristina Bazgan, Sonia Toubaline, and Daniel Vanderpooten

  30. Feasibility-Based Bounds Tightening via Fixed Points
    Pietro Belotti, Sonia Cafieri, Jon Lee, and Leo Liberti

  31. Constrained Surface-Level Gateway Placement for Underwater Acoustic Wireless Sensor Networks
    Deying Li, Zheng Li, Wenkai Ma and Hong Chen

  32. A New Result on [k,k+1]-Factors Containing Given Hamiltonian Cycles
    Guizhen Liu, Xuejun Pan, and Jonathan Z. Sun

  33. Time Optimal Algorithms for Black Hole Search in Rings
    Balasingham Balamohan, Paola Flocchini, Ali Miri, and Nicola Santoro  

  34. Bounded Length, 2-Edge Augmentation of Geometric Planar Graphs
    Evangelos Kranakis, Danny Krizanc, Oscar Morales, and Ladislav Stacho

  35. Strong Connectivity in Sensor Networks with Given Number of Directional Antennae of Bounded Angle
    Stefan Dobrev, Evangelos Kranakis, Danny Krizanc, Jaroslav Opatrny, Oscar Morales, and Ladislav Stacho

  36. Minimizing the Maximum Duty for Connectivity in Multi-Interface Networks
    Gianlorenzo D'Angelo, Gabriele Di Stefano, and Alfredo Navarra

  37. Yao Graphs Span Theta Graphs
    Mirela Damian and Kristin Raudonis

  38. A Simpler Algorithm for the All Pairs Shortest Path Problem with O(n^2log n) Expected Time
    Tadao Takaoka and Mashitoh Hashim

  39. A Transformation from PPTL to S1S
    Cong Tian and Zhenhua Duan

  40. New Min-Max Theorems for Weakly Chordal Graphs and Dually Chordal Graphs, and a New Class of Hypergraphs
    Arthur H. Busch, Feodor E. Dragan, and R. Sritharan

  41. Bounds for Nonadaptive Group Tests to Estimate the Amount of Defectives
    Peter Damaschke and Azam Sheikh Muhammad 

  42. A Simpler and More Efficient Algorithm for The Next-To-Shortest Path Problem
    Bang Ye Wu

  43. Fast Searching and Related Problems on Graphs
    Boting Yang

  44. A Characterisation of Stable Sets in Game with Transitive Preference
    Takashi Matsuhisa

  45. A Novel Branching Strategy for Parameterized Graph Modification Problems
    James Nastos and Yong Gao

  46. Listing Triconnected Rooted Plane Graphs
    Bingbing Zhuang and Hiroshi Nagamochi

  47. A Divide-and-Conquer Algorithm for Computing A Most Reliable Source on An Unreliable Ring-Embedded Tree
    Wei Ding and Guoliang Xue

  48. Linear Coherent Bi-Cluster Discovery via Beam Detection and Sample Set Clustering
    Yi Shi, Maryam Hasan, Zhipeng Cai, Guohui Lin, and Dale Schuurmans

  49. A Search-Based Approach to The Railway Rolling Stock Allocation Problem
    Tomoshi Otsuki, Hideyuki Aisu, and Toshiaki Tanaka

  50. Bipartite Permutation Graphs are Reconstructible
    Masashi Kiyomi, Toshiki Saitoh, and Ryuhei Uehara

  51. Constrained Low-Interference Relay Node Deployment for Underwater Acoustic Wireless Sensor Networks
    Deying Li, Zheng Li, Wenkai Ma, and Wenping Chen

  52. Structural Overlay Network for File Distribution
    Hongbing Fan and Yu-Liang Wu

  53. Approximation Algorithm for The Minimum Directed Tree Cover
    Viet Hung Nguyen

  54. Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs
    Mingyu Xiao

  55. Optimal Balancing of Satellite Queues in Packet Transmission to Ground Stations
    Evangelos Kranakis, Danny Krizanc, Ioannis Lambadaris, Lata Narayanan, and Jaroslav Opatrny

  56. An Iterative Algorithm of Computing The Transitive Closure of A Union of Parameterized Affine Integer Tuple Relations
    Bielecki Wlodzimierz , Klimek Tomasz, Palkowski Marek, and Anna Beletska

  57. The Bases of Primitive Non-Powerful Sign Pattern Matrices
    Guanglong Yu, Zhengke Miao, and Jinlong Shu


Accepted Papers - Short Papers

  1. Termination of Multipartite Graph Series Arising from Complex Network Modelisation
    Matthieu Latapy, Thi Ha Duong Phan, Christophe Crespelle, and Thanh Qui Nguyen

  2. Simpler Cuts are Fast and Good: Optimum Right-Angled Cuts in Solid Grids
    Andreas Emil Feldmann, Shantanu Das, and Peter Widmayer

  3. Evacuation of Rectilinear Polygons
    Sándor Fekete, Chris Gray, and Alexander Kroeller

  4. A Constant Approximation Algorithm for the Link Building Problem
    Martin Olsen, Anastasios Viglas, and Ilia Zvedeniouk

  5. Fast Algorithms for Alliances in Trees
    Ararat Harutyunyan

  6. XML Reconstruction View Selection in XML Databases: Complexity Analysis and Approximation Scheme
     Artem Chebotko and Bin Fu

  7. NP-Completeness of Spreading Colored Points
    Jun Luo, Ovidiu Daescu, and Wenqi Ju

  8. Computational Study for Planar Connected Dominating Set Problem
    Marjan Marzban, Qianping Gu, and Xiaohua Jia