Frontiers in Algorithmics and Algorithmic Aspects in Information and Management: Joint International Conference, FAW-AAIM 2011, Jinhua, China, May 28-31, 2011, Proceedings

by Mikhail Atallah (Editor), Xiang-Yang Li (Editor), Binhai Zhu (Editor)

Overview

This book constitutes the joint refereed proceedings of the 5th International Frontiers of Algorithmics Workshop, FAW 2011, and the 7th International Conference on Algorithmic Aspects in Information and Management, AAIM 2011, jointly held in Jinhua, China, in May 2011. The 35 revised full papers presented together with 4 invited talks were carefully reviewed and selected from 92 submissions. The papers cover a wide range of topics in the areas of algorithmics, combinatorial optimization and their applications presenting current trends of research.

Product Details

ISBN-13:	9783642212031
Publisher:	Springer Berlin Heidelberg
Publication date:	07/07/2011
Series:	Lecture Notes in Computer Science , #6681
Edition description:	2011
Pages:	390
Product dimensions:	6.10(w) x 9.25(h) x 0.04(d)

Table of Contents

Invited Lectures

Progress in Complexity of Counting Problems Jin-Yi Cai 1

Recent Developments in the Theory of Pre-processing Michael R. Fellows 4

Recent Developments in the Mechanism Design Problem for Scheduling Elias Koutsoupias 6

Degree-Driven Design for Correct Geometric Algorithms Jack Snoeyink 8

Contributed Papers

Approximation Algorithm for the Uniform Bounded Facility Problem Kerui Weng 10

The k-Canadian Travelers Problem with Communication Huili Zhang Yinfeng Xu 17

An Improved Competitive Algorithm for One-Dimensional Incremental Median Problem Wenqiang Dai Yi Feng 29

Approximation Scheme for Scheduling Resumable Proportionally Deteriorating Jobs Wenchang Luo Lin Chen 36

An Improved Approximation Algorithm for the Complementary Maximal Strip Recovery Problem Zhong Li Randy Goebel Lusheng Wang Guohui Lin 46

Greedy Routing via Embedding Graphs onto Semi-metric Spaces Huaming Zhang Swetha Govindaiah 58

On Variants of the Spanning Star Forest Problem Jing He Hongyu Liang 70

An Implicit Degree Condition for Cyclability in Graphs Hao Li Wantao Ning Junqing Cai 82

Parallel Enumeration of Lattice Animals Gadi Aleksandrowicz Gill Barequet 90

Parameterized Edge Dominating Set in Cubic Graphs (Extended Abstract) Mingyu Xiao Hiroshi Nagamochi 100

On Some Geometric Problems of Color-Spanning Sets Chenglin Fan Wenqi Ju Jun Luo Binhai Zhu 113

Approximation Algorithms for Cutting a Convex Polyhedron Out of a Sphere Xuehou Tan Gangshan Wu 125

An Algorithm for Optimal Acyclic Edge-Colouring of Cubic Graphs Edita Mácajová Ján Mazák 136

Complexity of Total {k}-Domination and Related Problems Jing He Hongyu Liang 147

The Min-Power Multicast Problems in Wireless Ad Hoc Networks: A Parameterized View Weizhong Luo Jianxin Wang Qilong Feng Jiong Guo 156

Constant Sum Flows in Regular Graphs Tao-Ming Wang Shi- Wei Hu 168

2D Knapsack: Packing Squares Min Chen György Dósa Xin Han Chenyang Zhou Attila Benko 176

Tight Approximation Bounds for Greedy Frugal Coverage Algorithms Ioannis Caragiannis Christos Kaklamanis Maria Kyropoulou 185

Algorithms for Interval Structures with Applications Danny Z. Chen Ewa Misiolek 196

Single Machine Scheduling with an Operator Non-availability Period to Minimize Total Completion Time Yong Chen An Zhang Zhiyi Tan 208

PSAEC: An Improved Algorithm for Short Read Error Correction Using Partial Suffix Arrays Zhiheng Zhao Jianping Yin Yubin Zhan Wei Xiong Yong Li Fayao Liu 220

Two Hardness Results on Feedback Vertex Sets Wei Jiang Tian Liu Tienan Ren Ke Xu 233

Approximation Algorithms for Unrelated Machine Scheduling with an Energy Budget Lin Chen Wenchang Luo Guochuan Zhang 244

Plane-Filling Properties of Directed Figures Wlodzimierz Moczurad 255

An Iterative Method for Generating Loop Invariants Shikun Chen Zhoujun Li Xiaoyu Song Mengjun Li 264

Algorithms for Computing Bidirectional Best Hit r-Window Gene Clusters Trong Dao Le Melvin Zhang Hon Wai Leong 275

Contracted Webgraphs: Structure Mining and Scale-Freeness Yushi Uno Fumiya Oguri 287

Hardness of Finding Two Edge-Disjoint Min-Min Paths in Digraphs Longkun Guo Hong She 300

Online Algorithm for 1-Space Bounded Multi-dimensional Bin Packing Yong Zhang Francis Y.L. Chin Hing-Fung Ting Xin Han Zhuo Chang 308

Online Algorithms for Maximizing Weighted Throughput of Unit Jobs with Temperature Constraints Martin Birks Daniel Cole Stanley P. Y. Fung Huichao Xue 319

Temperature Aware Online Algorithms for Scheduling Equal Length Jobs Martin Birks Stanley P. Y. Fung 330

Visibility Testing and Counting Sharareh Alipour Alireza Zarei 343

The Nearest Neighbor Spearman Footrule Distance for Bucket, Interval, and Partial Orders Franz J. Brandenburg Andreas Gleiβner Andreas Hofmeier 352

Minimum Width Rectangular Annulus Joydeep Mukherjee Priya Ranjan Sinha Mahapatra Arindam Karmakar Sandip Das 364

An Experimental Study on Generating Planar Graphs Sascha Meinert Dorothea Wagner 375

Author Index 389