Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
Joint International Conference, FAW-AAIM 2011, Jinhua, China, May 28-31, 2011, Proceedings
Published on 30. May 2011
XIII, 390 pages
978-3-642-21204-8 (ISBN)
Description
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.
More details
Other editions
Additional editions
Mikhail Atallah | Xiang-Yang Li | Binhai Zhu
Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
Joint International Conference, FAW-AAIM 2011, Jinhua, China, May 28-31, 2011, Proceedings
Book
05/2011
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- Invited Lectures
- Progress in Complexity of Counting Problems
- References
- Recent Developments in the Theory of Pre-processing
- Summary
- Recent Developments in the Mechanism Design Problem for Scheduling
- References
- Degree-Driven Design for Correct Geometric Algorithms
- Contributed Papers
- Approximation Algorithm for the Uniform Bounded Facility Problem
- Introduction
- UBFLP Model
- Greedy Approximation Algorithm for UBFLP on General Graph
- Constant-Factor Approximation Algorithm for UBFLP on Plane
- Conclusion
- References
- The k-Canadian Travelers Problem with Communication
- Introduction
- Problem Description
- The k-Canadian Travelers Problem with Full Communication (P1)
- The k-Canadian Travelers Problem with Limited Communication (P2)
- Retrace-Alternating Strategy in Urban Environment
- Conclusion
- References
- An Improved Competitive Algorithm for One-Dimensional Incremental Median Problem
- Introduction
- Algorithm Description
- Competitive Ratio Analysis
- Proof of Lemma 1
- Conclusion
- References
- Approximation Scheme for Scheduling Resumable Proportionally Deteriorating Jobs
- Introduction
- Preliminaries
- The Complexity
- AnFPTAS
- Concluding Remarks
- References
- An Improved Approximation Algorithm for the Complementary Maximal Strip Recovery Problem
- Introduction
- Preliminaries
- Favorable Operations
- A 73-Approximation Algorithm
- The Approx-CMSR Algorithm
- Performance Analysis
- Conclusions
- References
- Greedy Routing via Embedding Graphs onto Semi-metric Spaces
- Introduction
- Greedy Drawing in the Euclidean Spaces
- Succinctness in Greedy Drawing
- Succinct-Greedy Drawing in the Hyperbolic Plane
- Our Approach and Results
- Greedy Routing via Embedding Graphs into Semi-metric Spaces
- Greedy Routing via Semi-metric Spaces
- A Group of Semi-metric Spaces
- A Simple Greedy Routing Algorithm for Arbitrary Trees
- Greedy Routing for Connected Graphs
- References
- On Variants of the Spanning Star Forest Problem
- Introduction
- Our Contributions
- Notation Used for Approximation Algorithms
- Spanning Star Forest in Graphs with Minimum Degree Constraints
- Spanning k-Tree Forest Problem
- Improved Approximation Algorithm
- Inapproximability Results
- Improved Hardness Results for Spanning Star Forest
- References
- An Implicit Degree Condition for Cyclability in Graphs
- Introduction
- The Proof of Theorem 6
- References
- Parallel Enumeration of Lattice Animals
- Introduction
- Redelmeier's Algorithm
- Parallelism
- Results
- References
- Parameterized Edge Dominating Set in Cubic Graphs
- Introduction
- Enumeration-Based Algorithms
- Branching on Graphs of Maximum Degree 2
- Some Techniques
- The Algorithm
- Dealing with Leaf 6-Cycles
- Dealing with Leaf 7-Cycles
- Dealing with (3,0) Vertices
- Branching Rules in Step 7
- Branching Rules in Step 8
- Branching Rules in Step 9
- The Finial Result
- Concluding Remarks
- References
- On Some Geometric Problems of Color-Spanning Sets
- Introduction
- Computing the Maximum Diameter Color-Spanning Set
- Hardness of the LCPCS Problem
- NP-hardness for the Planar Minimum Color-Spanning Tree Problem
- NPO-hardness for PMCST
- Conclusions
- References
- Approximation Algorithms for Cutting a Convex Polyhedron Out of a Sphere
- Introduction
- Preliminaries
- Lower Bounds
- An Efficient O(n logn) Time Approximation Algorithm
- Box Cutting Phase
- Carving Phase
- Constant and O(logn) Factor Approximation Algorithms
- A General Property
- Algorithms in the Carving Phase
- Concluding Remarks
- References
- An Algorithm for Optimal Acyclic Edge-Colouring of Cubic Graphs
- Introduction
- The Algorithm
- The Complexity of the Algorithm
- References
- Complexity of Total {k}-Domination and Related Problems
- Introduction
- Preliminaries
- Summary of Our Contributions
- {k}-Domination and Total {k}-Domination
- NP-Completeness Results
- Approximation Results
- Total {k}-Domatic Number
- References
- The Min-Power Multicast Problems in Wireless Ad Hoc Networks: A Parameterized View
- Introduction
- Graph Model and Related Definitions
- Min-power Single-source h-Multicast is in FPT
- Reduction to Hop-bounded Directed Steiner Subgraph
- Solving Hop-Bounded Directed Steiner Subgraph
- Solving Min-power Single-source h-Multicast
- Parameterized Hardness Results
- Conclusions
- References
- Constant Sum Flows in Regular Graphs
- Introduction and Preliminaries
- Constant-Sum Flows for Regular Graphs
- Odd Regular Graphs
- Even Regular Graphs
- Concluding Remarks
- References
- 2D Knapsack: Packing Squares
- Introduction
- Preliminaries and Models
- A Simple Algorithm IHS and Its Applications
- Increasing Height Shelf
- IHS Algorithm for Packing Small Items
- A Modified IHS Algorithm for Packing Small Items
- A Simple Polynomial Time Approximation Scheme
- References
- Tight Approximation Bounds for Greedy Frugal Coverage Algorithms
- Introduction
- The Greedy Algorithm
- The Parameterized LP Lemma
- The Upper Bound
- Adding a Corrective Phase
- The Parameterized LP Lemma
- The Upper Bound
- Extensions
- References
- Algorithms for Interval Structures with Applications
- Introduction
- The Single-source K-link Shortest Path Problem on Interval Graphs
- Some Useful Structures of K-link Shortest Paths in I
- The O(Kn) Time K-SP Algorithm
- The Generalized Optimal Color-Spanning Problem
- The Two-Scan G-OCS Algorithm
- The One-Scan G-OCS Algorithm
- References
- Single Machine Scheduling with an Operator Non-availability Period to Minimize Total Completion Time
- Introduction
- Problem and Algorithm
- Preliminary Results
- Proof of the Worst-Case Ratio
- References
- PSAEC: An Improved Algorithm for Short Read Error Correction Using Partial Suffix Arrays
- Introduction
- Background
- Notations and Suffix Array
- The HiTEC Algorithm
- PSAEC
- Methods
- Algorithm
- Parallelization
- Experiments
- Conclusion
- References
- Two Hardness Results on Feedback Vertex Sets
- Introduction
- The Reduction
- The Lower Bounds
- In G(n,p)
- In GRB(n,r)
- Open Problems
- References
- Approximation Algorithms for Unrelated Machine Scheduling with an Energy Budget
- Introduction
- The Continuous Model
- The Discrete Model
- A 2-Approximation Algorithm with Energy Augmentation
- Concluding Remarks
- References
- Plane-Filling Properties of Directed Figures
- Introduction
- Preliminaries
- Infinite and Semi-infinite Zippers
- Filling the Plane with Figures
- Final Remarks
- References
- An Iterative Method for Generating Loop Invariants
- Introduction
- Preliminaries
- Invariant Generation
- Solving Constraints
- Case Studies
- Conclusion
- References
- Algorithms for Computing Bidirectional Best Hit r-Window Gene Clusters
- Introduction
- Problem Formulation
- BBHRW Using Similarity Measure count
- Similarity Measure count
- Algorithm SWBST
- Time Complexity Analysis of Algorithm SWBST
- BBHRW Using Similarity Measure msint
- Similarity Measure msint
- Algorithm SWOT
- Time Complexity Analysis of Algorithm SWOT
- Results and Discussion
- Experimental Setup
- Comparison of the Running Time
- Characteristics of BBHRW Clusters for count and msint
- Conclusion
- References
- Contracted Webgraphs: Structure Mining and Scale-Freeness
- Introduction
- Contracted Webgraphs
- Undirected Webgraphs
- Intra-/Inter-domain Substructures and Contractions
- Contracted Webgraphs
- Isolated Cliques and Isolated Stars as Communities and Spams
- Outline of Experiments on Contracted Webgraphs
- Scale-Freeness of Contracted Webgraphs
- Properties of Isolated Clique Contracted Webgraphs
- Properties of Isolated Star Contracted Webgraphs
- Properties of Isolated Clique and Isolated Star Contracted Webgraphs
- Scale-Freeness and Self-similarities in Contracted Webgraphs
- Structure Mining on Contracted Webgraphs
- Structure Mining on Isolated Clique Contracted Webgraphs
- Structure Mining on Isolated Star Contracted Webgraphs
- Structure Mining on Isolated Clique and Isolated Star Contracted Webgraphs
- Validity of Contracted Webgraphs for Structure Mining
- Concluding Remarks
- References
- Hardness of Finding Two Edge-Disjoint Min-Min Paths in Digraphs
- Introduction
- A Simpler NP-Completeness Proof for the Edge-Disjoint Min-Min Problem in General Digraphs
- Extension of the Proof to Planar Digraphs
- Conclusion
- References
- Online Algorithm for 1-Space Bounded Multi-dimensional Bin Packing
- Introduction
- Preliminary
- Packing Strategy
- Analysis of the Strategy
- References
- Online Algorithms for Maximizing Weighted Throughput of Unit Jobs with Temperature Constraints
- Introduction
- Deterministic Case
- Randomized Case: Full Heat
- Randomized Case: Non-full Heat
- Multiple Processors
- Conclusion
- References
- Temperature Aware Online Algorithms for Scheduling Equal Length Jobs
- Introduction
- The Nonpreemptive Model
- Lower Bound
- Upper Bound: Coolest First
- Upper Bound: Any Reasonable Algorithm
- The Preemptive Restart Model
- The Preemptive Resume Model
- References
- Visibility Testing and Counting
- Introduction
- The Visibility Testing Problem
- The Visibility Counting Problem
- Conclusion
- References
- The Nearest Neighbor Spearman Footrule Distance for Bucket, Interval, and Partial Orders
- Introduction
- Preliminaries
- Distance Problems
- Rank Aggregation Problem
- Approximation Algorithms
- Conclusion and Open Problems
- References
- Minimum Width Rectangular Annulus
- Introduction
- Problem Definition and Notations
- Axis-Parallel Annulus
- Arbitrarily Oriented Annulus
- Algorithm and Complexity
- Conclusion
- References
- An Experimental Study on Generating Planar Graphs
- Introduction
- Graph Generators
- (n)-generators
- (n,m)-generators
- Summary
- Experiments
- Dataset Generation
- Basic Graph Properties
- Algorithmical Behavior
- Conclusions
- References
- Author Index
