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

by Atallah, Mikhail; Li, Xiang-yang; Zhu, Binhai

• ISBN13: 9783642212031
• ISBN10: 3642212034
• Edition: 1st
• Format: Paperback
• Copyright: 2011-07-07
• Publisher: Springer-Verlag New York Inc

Summary

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.

Table of Contents

Invited Lectures
Progress in Complexity of Counting Problems	p. 1
Recent Developments in the Theory of Pre-processing	p. 4
Recent Developments in the Mechanism Design Problem for Scheduling	p. 6
Degree-Driven Design for Correct Geometric Algorithms	p. 8
Contributed Papers
Approximation Algorithm for the Uniform Bounded Facility Problem	p. 10
The k-Canadian Travelers Problem with Communication	p. 17
An Improved Competitive Algorithm for One-Dimensional Incremental Median Problem	p. 29
Approximation Scheme for Scheduling Resumable Proportionally Deteriorating Jobs	p. 36
An Improved Approximation Algorithm for the Complementary Maximal Strip Recovery Problem	p. 46
Greedy Routing via Embedding Graphs onto Semi-metric Spaces	p. 58
On Variants of the Spanning Star Forest Problem	p. 70
An Implicit Degree Condition for Cyclability in Graphs	p. 82
Parallel Enumeration of Lattice Animals	p. 90
Parameterized Edge Dominating Set in Cubic Graphs (Extended Abstract)	p. 100
On Some Geometric Problems of Color-Spanning Sets	p. 113
Approximation Algorithms for Cutting a Convex Polyhedron Out of a Sphere	p. 125
An Algorithm for Optimal Acyclic Edge-Colouring of Cubic Graphs	p. 136
Complexity of Total {k}-Domination and Related Problems	p. 147
The Min-Power Multicast Problems in Wireless Ad Hoc Networks: A Parameterized View	p. 156
Constant Sum Flows in Regular Graphs	p. 168
2D Knapsack: Packing Squares	p. 176
Tight Approximation Bounds for Greedy Frugal Coverage Algorithms	p. 185
Algorithms for Interval Structures with Applications	p. 196
Single Machine Scheduling with an Operator Non-availability Period to Minimize Total Completion Time	p. 208
PSAEC: An Improved Algorithm for Short Read Error Correction Using Partial Suffix Arrays	p. 220
Two Hardness Results on Feedback Vertex Sets	p. 233
Approximation Algorithms for Unrelated Machine Scheduling with an Energy Budget	p. 244
Plane-Filling Properties of Directed Figures	p. 255
An Iterative Method for Generating Loop Invariants	p. 264
Algorithms for Computing Bidirectional Best Hit r-Window Gene Clusters	p. 275
Contracted Webgraphs: Structure Mining and Scale-Freeness	p. 287
Hardness of Finding Two Edge-Disjoint Min-Min Paths in Digraphs	p. 300
Online Algorithm for 1-Space Bounded Multi-dimensional Bin Packing	p. 308
Online Algorithms for Maximizing Weighted Throughput of Unit Jobs with Temperature Constraints	p. 319
Temperature Aware Online Algorithms for Scheduling Equal Length Jobs	p. 330
Visibility Testing and Counting	p. 343
The Nearest Neighbor Spearman Footrule Distance for Bucket, Interval, and Partial Orders	p. 352
Minimum Width Rectangular Annulus	p. 364
An Experimental Study on Generating Planar Graphs	p. 375
Author Index	p. 389
Table of Contents provided by Ingram. All Rights Reserved.