Computing and Combinatorics 2005

Constitutes the proceedings of the 11th Annual International Computing and Combinatorics Conference, COCOON 2005, held in Kunming, China in August 2005. This title contains 96 revised papers presented together with abstracts of 3 invited talks which cover various aspects of theoretical computer science and combinatorics related to computing. The papers in this volume were presented at the Eleventh Annual International ComputingandCombinatorics Conference(COCOON2005),heldAugust16-19, 2005,in Kunming, China. The topicscovermost aspects oftheoreticalcomputer science and combinatorics related to computing. Submissionstotheconferencethisyearwereconductedelectronically.Atotal of 353 papers were submitted, of which 96 were accepted. So the competition is very ?erce. The papers were evaluated by an international program committee consisting of Tatsuya Akutsu, Vineet Bafna, Zhi-Zhong Chen, Siu-Wing Cheng, Francis Chin, Sunghee Choi, Bhaskar DasGupta, Qizhi Fang, Martin Farach- Colton, Ra?aele Giancarlo, Mordecai Golin, Peter Hammer, Tsan-sheng Hsu, Sorin C. Istrail, Samir Khuller, Michael A. Langston, Jianping Li, Weifa Liang, GuohuiLin, BernardMans,SatoruMiyano,C.K.Poon,R.Ravi,DavidSanko?, Shang-Hua Teng, H. F. Ting, Seinosuke Toda, Takeshi Tokuyama, Peng-Jun Wan, Lusheng Wang, Todd Wareham, Jinhui Xu, Xizhong Zheng, Kaizhong Zhang and Binhai Zhu. The authors of submitted papers came from more than 25 countries and regions. In addition to the selected papers, the conference also included three invited presentations by Alberto Apostolico, Shang-Hua Teng, and Leslie G. Valiant. This year's Wang Hao Award (for young researchers) was given to the paperApproximatingtheLongestCycle Problem onGraphs with BoundedDegree by Guantao Chen, Zhicheng Gao, Xingxing Yu and Wenan Zang. I would like to thank all the people who made this meeting possible and - joyable:the authors for submitting papers and the programcommittee members andexternalrefereesfor their excellentwork.I wouldalsoliketo thank thethree invited speakers and the local organizers and colleagues for their assistance.