Combinatorial Optimization and Applications

1. Front Matter

   PDF

2. The Complexity of Testing Monomials in Multivariate Polynomials

   • Zhixiang Chen, Bin Fu

   Pages 1-15

3. Algorithms for Testing Monomials in Multivariate Polynomials

   • Zhixiang Chen, Bin Fu, Yang Liu, Robert Schweller

   Pages 16-30

4. Hybrid Artificial Bee Colony Search Algorithm Based on Disruptive Selection for Examination Timetabling Problems

   • Malek Alzaqebah, Salwani Abdullah

   Pages 31-45

5. Heuristics for Parallel Machine Scheduling with Deterioration Effect

   • Ming Liu, Feifeng Zheng, Yinfeng Xu, Lu Wang

   Pages 46-51

6. A Comprehensive Study of an Online Packet Scheduling Algorithm

   • Fei Li

   Pages 52-63

7. Optimal Policy for Single-Machine Scheduling with Deterioration Effects, Learning Effects, Setup Times, and Availability Constraints

   • Sheng Yu, Yinfeng Xu, Ming Liu, Feifeng Zheng

   Pages 64-73

8. Algebraic Algorithm for Scheduling Data Retrieval in Multi-channel Wireless Data Broadcast Environments

   • Xiaofeng Gao, Zaixin Lu, Weili Wu, Bin Fu

   Pages 74-81

9. Hamiltonian Cycles through Prescribed Edges in k-Ary n-Cubes

   • Iain A. Stewart

   Pages 82-97

10. A Fast Parallel Algorithm for Finding a Most Reliable Source on a General Ring-Tree Graph with Unreliable Edges

    • Wei Ding, Guoliang Xue

    Pages 98-112

11. Restricted Edge Connectivity of Harary Graphs

    • Qinghai Liu, Xiaohui Huang, Zhao Zhang

    Pages 113-125

12. Efficient Algorithms for Finding the k Most Vital Edges for the Minimum Spanning Tree Problem

    • Cristina Bazgan, Sonia Toubaline, Daniel Vanderpooten

    Pages 126-140

13. Euclidean Chains and Their Shortcuts

    • Boting Yang

    Pages 141-155

14. List Dynamic Coloring of Sparse Graphs

    • Seog-Jin Kim, Won-Jin Park

    Pages 156-162

15. Further Improvement on Maximum Independent Set in Degree-4 Graphs

    • Mingyu Xiao, Hiroshi Nagamochi

    Pages 163-178

16. Approximation Algorithms for Minimum Energy Multicast Routing with Reception Cost in Wireless Sensor Networks

    • Deying Li, Zewen Liu, Yi Hong, Wenping Chen

    Pages 179-191

17. Public Communication Based on Russian Cards Protocol: A Case Study

    • Jia He, Zhenhua Duan

    Pages 192-206

18. Minimum Latency Data Aggregation in Wireless Sensor Network with Directional Antenna

    • Hui Liu, Zewen Liu, Hongwei Du, Deying Li, Xianling Lu

    Pages 207-221

19. A Near-Optimal Memoryless Online Algorithm for FIFO Buffering Two Packet Classes

    • Fei Li

    Pages 222-233

20. On the Maximum Locally Clustered Subgraph and Some Related Problems

    • Bang Ye Wu

    Pages 234-246

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.

• computational geometry
• graph algorithms
• integer programming
• parallel computing
• wireless sensor networks
• algorithm analysis and problem complexity

• Zhejiang Normal University, Jinhua, China

  Weifan Wang, Xuding Zhu

• Department of Computer Science, University of Texas at Dallas, Richardson, USA

  Ding-Zhu Du

Policies and ethics