Andreas Dress Yinfeng Xu Binhai Zhu (Eds.)
Combinatorial Optimization and Applications First International Conference, COCOA 2007 Xi’an, China, August 14-16, 2007 Proceedings
13
Volume Editors Andreas Dress CAS-MPG Partner Institute for Computational Biology Shanghai 200031, China and Max Planck Institute for Mathematics in the Sciences D-04104 Leipzig, Germany E-mail:
[email protected] Yinfeng Xu Xi’an Jiaotong University Xi’an, Shaanxi 710049, China E-mail:
[email protected] Binhai Zhu Montana State University Bozeman, MT 59717, USA E-mail:
[email protected]
Library of Congress Control Number: 2007931336 CR Subject Classification (1998): F.2, C.2, G.2-3, I.3.5, G.1.6, E.5 LNCS Sublibrary: SL 1 – Theoretical Computer Science and General Issues ISSN ISBN-10 ISBN-13
0302-9743 3-540-73555-0 Springer Berlin Heidelberg New York 978-3-540-73555-7 Springer Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. Springer is a part of Springer Science+Business Media springer.com © Springer-Verlag Berlin Heidelberg 2007 Printed in Germany Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India Printed on acid-free paper SPIN: 12088744 06/3180 543210
Preface
The papers in this volume were presented at the 1st International Conference on Combinatorial Optimization and Applications (COCOA 2007), held August 12-15, 2007, in Xi’an, China. The topics cover most areas in combinatorial optimization and applications. Submissions to the conference this year were conducted electronically. A total of 114 papers were submitted, of which 29 were accepted. The papers were evaluated by an International Program Committee consisting of Tetsuo Asano, Kyung-Yong Chwa, Bill Chen, Bo Chen, Andreas Dress, Pater Eades, Omer Egecioglu, Rudolf Fleischer, Bin Fu, Mordecai Golin, Ron Graham, Pavol Hell, Xiao-Dong Hu, Marek Karpinski, Minghui Jiang, Michael Langston, Hanno Lefmann, Ko-Wei Lih, Andy Mirzaian, Brendan Mumey, Mauricio G.C. Resende, Takao Nishizeki, Mike Steel, Zheng Sun, My T. Thai, Kanliang Wang, Michael Waterman, Gerhard Woeginger, Yinfeng Xu, Boting Yang, Wenan Zang, Alex Zelikovsky and Binhai Zhu. It is expected that most of the accepted papers will appear in a more complete form in scientific journals. The submitted papers are from Australia, Canada, China, France, Germany, Greece, Hong Kong, Japan, Korea, Mexico, Poland, Romania, Russia, Switzerland, Tunisia, Turkey and USA. Each paper was evaluated by at least two Program Committee members (and in some cases by as many as seven Program Committee members), assisted in some cases by subreferees. In addition to selected papers, the conference also included two invited presentations, by Bailin Hao and Kurt Mehlhorn, and eight invited papers. We thank all the people who made this meeting possible: the authors for submitting papers, the Program Committee members and external referees (listed in the proc