Dingzhu Du Knihy

This book constitutes the refereed proceedings of the Third International Conference on Combinatorial Optimization and Applications, COCOA 2009, held in Huangshan, China, in June 2009. The 50 revised full papers were carefully reviewed and selected from 103 submissions. The papers feature original research in the areas of combinatorial optimization - both theoretical issues and and applications motivated by real-world problems thus showing convincingly the usefulness and efficiency of the algorithms discussed in a practical setting.

Focusing on the intersection of operations research, computer science, and applied mathematics, this book delves into combinatorial optimization, highlighting its significance in diverse applications such as network design, scheduling, and computational biology. It traces the historical roots of the field to linear programming, noting key advancements like the ellipsoid method and interior point approaches that have revolutionized problem-solving. The text emphasizes the commonality of discrete problems and their connection to linear programming, including the development of approximation algorithms for NP-hard issues.

The textbook uniquely categorizes approximation algorithms by their design techniques, enabling readers to explore similar algorithms in a cohesive manner. This structured approach differentiates it from other theoretical computer science resources, facilitating a deeper understanding of the algorithms' underlying principles and applications.

Combinatorial optimization is a dynamic field at the intersection of operations research, computer science, and applied mathematics, with applications ranging from network design to machine vision and scheduling. It encompasses diverse areas like linear and integer programming, graph theory, and artificial intelligence. The discipline evolved from linear programming, which has significant applications in resource allocation and planning. Key developments, such as the ellipsoid method and interior point approaches, have introduced polynomial-time algorithms that greatly influence combinatorial optimization solutions.

This book serves as a textbook for graduate students in theoretical computer science and a reference for researchers on approximation algorithms. Unlike existing problem-oriented texts, it offers a structured, technique-oriented approach, organizing algorithms by design techniques to enhance understanding and teaching of the subject.

The connected dominating set has been a classic subject studied in graph theory since 1975. Since the 1990s, it has been found to have important applications in communication networks, especially in wireless networks, as a virtual backbone. Motivated from those applications, many papers have been published in the literature during last 15 years. Now, the connected dominating set has become a hot research topic in computer science. In this book, we are going to collect recent developments on the connected dominating set, which presents the state of the art in the study of connected dominating sets. The book consists of 16 chapters. Except the 1st one, each chapter is devoted to one problem, and consists of three parts, motivation and overview, problem complexity analysis, and approximation algorithm designs, which will lead the reader to see clearly about the background, formulation, existing important research results, and open problems. Therefore, this would be a very valuable reference book for researchers in computer science and operations research, especially in areas of theoretical computer science, computer communication networks, combinatorial optimization, and discrete mathematics.

The papers in this volume were selected for presentation at the 6th Annual International Computing and Combinatorics Conference (COCOON2000), in Sydney, Australia from July 26 - 28, 2000. The topics cover many areas in t- oretical computer science and combinatorial optimization. There were 81 high quality papers submitted to COCOON2000. Each paper was reviewed by at least three program committee members, and the 44 papers were selected. It is expected that most of them will appear in a more complete form in scientic journals. In addition to the selected papers, the volume also contains the papers from two invited keynote speeches by Christos Papad- itriou and Richard Brent. This year the Hao Wang Award was given to honor the paper judged by the programcommittee to have the greatest merit. The recipient is \Approximating Uniform TriangularMeshes in Polygons"byFranz Aurenhammer, NaokiKatoh, Hiromichi Kojima, Makoto Ohsaki, and Yinfeng Xu. The rst Best Young - searcher paper award was given to William Duckworth for his paper \Maximum Induced Matchings of Random Cubic Graphs". We wish to thank all who have made this meeting the authors for submitting papers, the program committee members and the external referees, sponsors, the local organizers, ACM SIGACT for handling electronic subm- sions, Springer-Verlagfor their support, and Debbie Hatherellfor her assistance.