Combinatorial Optimization and Applications: 5th International Conference, COCOA 2011, Zhangjiajie, China, August 4-6, 2011. Proceedings

✍ Scribed by Zhixiang Chen, Bin Fu (auth.), Weifan Wang, Xuding Zhu, Ding-Zhu Du (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2011
• Tongue: English
• Leaves: 575
• Series: Lecture Notes in Computer Science 6831
• Edition: 1
• Category: Library

✦ Synopsis

This book constitutes the refereed proceedings of the 5th International Conference on Combinatorial Optimization and Applications, COCOA 2011, held in Zhangjiajie, China, in August 2011. The 43 revised full papers were carefully reviewed and selected from 65 submissions. The papers cover a broad range of topics in combinatorial optimization and applications focussing on experimental and applied research of general algorithmic interest and research motivated by real-world problems.

✦ Table of Contents

Front Matter....Pages -
The Complexity of Testing Monomials in Multivariate Polynomials....Pages 1-15
Algorithms for Testing Monomials in Multivariate Polynomials....Pages 16-30
Hybrid Artificial Bee Colony Search Algorithm Based on Disruptive Selection for Examination Timetabling Problems....Pages 31-45
Heuristics for Parallel Machine Scheduling with Deterioration Effect....Pages 46-51
A Comprehensive Study of an Online Packet Scheduling Algorithm....Pages 52-63
Optimal Policy for Single-Machine Scheduling with Deterioration Effects, Learning Effects, Setup Times, and Availability Constraints....Pages 64-73
Algebraic Algorithm for Scheduling Data Retrieval in Multi-channel Wireless Data Broadcast Environments....Pages 74-81
Hamiltonian Cycles through Prescribed Edges in k -Ary n -Cubes....Pages 82-97
A Fast Parallel Algorithm for Finding a Most Reliable Source on a General Ring-Tree Graph with Unreliable Edges....Pages 98-112
Restricted Edge Connectivity of Harary Graphs....Pages 113-125
Efficient Algorithms for Finding the k Most Vital Edges for the Minimum Spanning Tree Problem....Pages 126-140
Euclidean Chains and Their Shortcuts....Pages 141-155
List Dynamic Coloring of Sparse Graphs....Pages 156-162
Further Improvement on Maximum Independent Set in Degree-4 Graphs....Pages 163-178
Approximation Algorithms for Minimum Energy Multicast Routing with Reception Cost in Wireless Sensor Networks....Pages 179-191
Public Communication Based on Russian Cards Protocol: A Case Study....Pages 192-206
Minimum Latency Data Aggregation in Wireless Sensor Network with Directional Antenna....Pages 207-221
A Near-Optimal Memoryless Online Algorithm for FIFO Buffering Two Packet Classes....Pages 222-233
On the Maximum Locally Clustered Subgraph and Some Related Problems....Pages 234-246
Quickest Paths in Anisotropic Media....Pages 247-261
Mechanisms for Obnoxious Facility Game on a Path....Pages 262-271
Algorithmic Aspects of Heterogeneous Biological Networks Comparison....Pages 272-286
Minimum Interval Cover and Its Application to Genome Sequencing....Pages 287-298
Exponential and Polynomial Time Algorithms for the Minimum Common String Partition Problem....Pages 299-310
Complexity of the Stamp Folding Problem....Pages 311-321
On the Number of Solutions of the Discretizable Molecular Distance Geometry Problem....Pages 322-342
Integration of an LP Solver into Interval Constraint Propagation....Pages 343-356
A Saturation Algorithm for Homogeneous Binomial Ideals....Pages 357-371
Improved Algorithms for Farthest Colored Voronoi Diagram of Segments....Pages 372-386
One-and-a-Half-Side Boundary Labeling....Pages 387-398
Approximation Algorithms for a Bi-level Knapsack Problem....Pages 399-410
On the Surface Area of the Asymmetric Twisted Cube....Pages 411-423
Tractable Feedback Vertex Sets in Restricted Bipartite Graphs....Pages 424-434
On the Partition of 3-Colorable Graphs....Pages 435-447
Kinetic Red-Blue Minimum Separating Circle....Pages 448-463
A Semantic Model for Many-Core Parallel Computing....Pages 464-479
On Unique Games with Negative Weights....Pages 480-490
A Note on Treewidth in Random Graphs....Pages 491-499
On the Two-Stage Stochastic Graph Partitioning Problem....Pages 500-509
A Spatio-Temporal Approach to the Discovery of Online Social Trends....Pages 510-524
A New Approximation Algorithm for the Selective Single-Sink Buy-at-Bulk Problem in Network Design....Pages 525-536
Greedy Algorithm for Least Privilege in RBAC Model....Pages 537-545
Towards Minimum Delay Broadcasting and Multicasting in Multihop Wireless Networks....Pages 546-560
Back Matter....Pages -

✦ Subjects

Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Numeric Computing; Computer Communication Networks; Computer Graphics; Algorithms