Frontiers in algorithmics and algorithmic aspects in information and management : joint international conference, FAW-AAIM 2011, Jinhua, China, May 28-31, 2011 ; proceedings

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. Front Matter....Pages - Progress in Complexity of Counting Problems....Pages 1-3 Recent Developments in the Theory of Pre-processing....Pages 4-5 Recent Developments in the Mechanism Design Problem for Scheduling....Pages 6-7 Degree-Driven Design for Correct Geometric Algorithms....Pages 8-9 Approximation Algorithm for the Uniform Bounded Facility Problem....Pages 10-16 The k-Canadian Travelers Problem with Communication....Pages 17-28 An Improved Competitive Algorithm for One-Dimensional Incremental Median Problem....Pages 29-35 Approximation Scheme for Scheduling Resumable Proportionally Deteriorating Jobs....Pages 36-45 An Improved Approximation Algorithm for the Complementary Maximal Strip Recovery Problem....Pages 46-57 Greedy Routing via Embedding Graphs onto Semi-metric Spaces....Pages 58-69 On Variants of the Spanning Star Forest Problem....Pages 70-81 An Implicit Degree Condition for Cyclability in Graphs....Pages 82-89 Parallel Enumeration of Lattice Animals....Pages 90-99 Parameterized Edge Dominating Set in Cubic Graphs....Pages 100-112 On Some Geometric Problems of Color-Spanning Sets....Pages 113-124 Approximation Algorithms for Cutting a Convex Polyhedron Out of a Sphere....Pages 125-135 An Algorithm for Optimal Acyclic Edge-Colouring of Cubic Graphs....Pages 136-146 Complexity of Total { k }-Domination and Related Problems....Pages 147-155 The Min-Power Multicast Problems in Wireless Ad Hoc Networks: A Parameterized View....Pages 156-167 Constant Sum Flows in Regular Graphs....Pages 168-175 2D Knapsack: Packing Squares....Pages 176-184 Tight Approximation Bounds for Greedy Frugal Coverage Algorithms....Pages 185-195 Algorithms for Interval Structures with Applications....Pages 196-207 Single Machine Scheduling with an Operator Non-availability Period to Minimize Total Completion Time....Pages 208-219 PSAEC: An Improved Algorithm for Short Read Error Correction Using Partial Suffix Arrays....Pages 220-232 Two Hardness Results on Feedback Vertex Sets....Pages 233-243 Approximation Algorithms for Unrelated Machine Scheduling with an Energy Budget....Pages 244-254 Plane-Filling Properties of Directed Figures....Pages 255-263 An Iterative Method for Generating Loop Invariants....Pages 264-274 Algorithms for Computing Bidirectional Best Hit r -Window Gene Clusters....Pages 275-286 Contracted Webgraphs: Structure Mining and Scale-Freeness....Pages 287-299 Hardness of Finding Two Edge-Disjoint Min-Min Paths in Digraphs....Pages 300-307 Online Algorithm for 1-Space Bounded Multi-dimensional Bin Packing....Pages 308-318 Online Algorithms for Maximizing Weighted Throughput of Unit Jobs with Temperature Constraints....Pages 319-329 Temperature Aware Online Algorithms for Scheduling Equal Length Jobs....Pages 330-342 Visibility Testing and Counting....Pages 343-351 The Nearest Neighbor Spearman Footrule Distance for Bucket, Interval, and Partial Orders....Pages 352-363 Minimum Width Rectangular Annulus....Pages 364-374 An Experimental Study on Generating Planar Graphs....Pages 375-387 Back Matter....Pages -