This book constitutes the refereed proceedings of the First International Conference on Combinatorial Optimization and Applications, COCOA 2007, held in Xi'an, China in August 2007. The 29 revised full papers presented together with 8 invited papers and 2 invited presentations were carefully reviewed and selected from 114 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. Running to almost 400 pages, and featuring more than 40 papers, this work on combinatorial optimization and applications will be seen as an important addition to the literature. It constitutes the refereed proceedings of the first International Conference on Combinatorial Optimization and Applications, COCOA 2007, held in Xi'an, China in August of that year. The 29 revised full papers presented together with 8 invited papers and 2 invited presentations were carefully reviewed and selected from 114 submissions and cover both theoretical issues and practical applications. Invited Lecture Matchings in Graphs Variations of the Problem 1 Kurt Mehlhorn Combinatorics from Bacterial Genomes 3 Bailin Hao Contributed Papers An Algorithm for Computing Virtual Cut Points in Finite Metric Spaces 4 Andreas W.M. Dress, Katharina T. Huber, Jacobus Koolen, and Vincent Moulton Finding the Anti-block Vital Edge of a Shortest Path Between Two Nodes 11 Bing Su, Qingchuan Xu, and Peng Xiao K-Connected Target Coverage Problem in Wireless Sensor Networks 20 Deying Li, Jiannong Cao, Ming Liu, and Yuan Zheng Searching Cycle-Disjoint Graphs 32 Boting Yang, Runtao Zhang, and Yi Cao An Asymptotic PTAS for Batch Scheduling with Nonidentical Job Sizes to Minimize Makespan 44 Yuzhong Zhang and Zhigang Cao A New Dynamic Programming Algorithm for Multiple Sequence Alignment 52 Jean-Michel Richer, Vincent Derrien, and Jin-Kao Hao Energy Minimizing Vehicle Routing Problem 62 Imdat Kara, Bahar Y. Kara, and M. Kadri Yetis On the On-Line k-Taxi Problem with Limited Look Ahead 72 Weimin Ma, Ting Gao, and Ke Wang The Minimum Risk Spanning Tree Problem 81 Xujin Chen, Jie Hu, and Xiaodong Hu The Size of a Minimum Critically m-Neighbor-Scattered Graph 91 Fengwei Li and Qingfang Ye A New Hybrid Algorithm for Feature Selection and Its Application to Customer Recognition 102 Luo Yan and Yu Changrui Steiner Forests on Stochastic Metric Graphs 112 Vangelis Th. Paschos, Orestis A. Telelis, and Vassilis Zissimopoulos On Threshold BDDs and the Optimal Variable Ordering Problem 124 Markus Behle Communication Leading to Nash Equilibrium Through Robust Messages S5-Knowledge Model Case 136 Takashi Matsuhisa Fundamental Domains for Integer Programs with Symmetries 146 Eric J. Friedman Exact Algorithms for Generalized Combinatorial Optimization Problems 154 Petrica C. Pop, Corina Pop Sitar, Ioana Zelina, and Mona Tascu Approximation Algorithms for k-Duplicates Combinatorial Auctions with Subadditive Bidders 163 Wenbin Chen and Jiangtao Meng A Grid Resource Discovery Method Based on Adaptive k-Nearest Neighbors Clustering 171 Yan Zhang, Yan Jia, Xiaobin Huang, Bin Zhou, and Jian Gu Algorithms for Minimum rn-Connected k-Dominating Set Problem 182 Weiping Shang, Frances Yao, Pengjun Wan, and Xiaodong Hu Worst Case Analysis of a New Lower Bound for Flow Shop Weighted Completion Time Problem 191 Danyn Bai and Lixin Tang Scaling, Renormalization, and Universality in Combinatorial Games: The Geometry of Chomp 200 Eric J. Friedman and Adam Scott Landsberq Mechanism Design by Creditability 208 Raphael Eidenbenz, Yvonne Anne Oswald, Stefan Schmid, and Roger Wattenhofer Infinite Families of Optimal Double-Loop Networks 220 Xiaoping Dar IiOnqin Zhou. and Xiaohn Wang Point Sets in the Unit Square and Large Areas of Convex Hulls of Subsets of Points 230 Hanno Lefmann. An Experimental Study of Compressed Indexing and Local Alignments of DNA 242 Tak-Wah Lam, Wing-Kin Sung, Siu-Lung Tarn, Chi-Kwong Wong. and Siu-Ming Yin Secure Multiparty Computations Using the 15 Puzzle (Extended Abstract) 255 Takaaki Mimi,* Yoshinori Kugimoto, and Hideaki Sone Lagrangian Relaxation Approach for the Multiple Sequence Alignment Problem 267 Ernst Althaus and Stefan Canzar Single Machine Common Due Window Scheduling with Controllable Job Processing Times 279 Guohua Wan A Lower Bound on Approximation Algorithms for the Closest Substring 291 Jianxin Wang, Min Huang, and Jianer Chen A New Exact Algorithm for the Two-Sided Crossing Minimization 301 Lank, Zheng and Christoph Buchheim Improved Approximation Algorithm for Connected Facility Location Problems (Extended Abstract) 311 Mohammad Khairul Has an, Hyunwoo Jung, and Kyung-Yong Chwa The Computational Complexity of Game Trees by Eigen-Distribution 323 ChenGuang Liu and Kazuyuki Tanaka The Minimum All-Ones Problem for Graphs with Small Treewidth 335 Yunting Lu and Yueping Li An Exact Algorithm Based on Chain Implication for the Min-CVCB Problem 343 Jianxin Wang, Xiaoshuang Xu, and Yunlong Liu Ard Searching Digraphs Without Jumping 354 Brian Alspach, Danny Dyer, Denis Hanson, and Boting Yang On the Complexity of Some Colorful Problems Parameterized by Treewidth 366 Michael Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances Rosamond, Saket Saurabh, Stefan Szeider, and Carsten Thomassen A PTAS for the Weighted 2-Interval Pattern Problem over the Preceding-and-Crossing Model 378 Minghui Jiang Author Index 389