Technical Program of COCOON 2006 August 15, Tuesday 7:00 - 9:00 pm: Reception August 16, Wednesday 8:50 - 9:00 am: Opening of COCOON'06 D.T. Lee 9:00 - 10:00 am: Invited Talk (Moderator: D. T. Lee) The Unpredictable Deviousness of Models Franco P. Preparata (Brown University, USA) 10:00 - 10:20 am: Break 10:20 am - 12:00 noon: Session A Computational Economics, Finance, and Management Session Chair: Ming-Yang Kao A Simplicial Approach for Discrete Fixed Point Theorems. Xi Chen (Tsinghua University, Beijing, P.R.China) Xiaotie Deng (City University of Hong Kong, Hong Kong, China) On Incentive Compatible Competitive Selection Protocol Xi Chen (Tsinghua University, Beijing, P.R.China) Xiaotie Deng (City University of Hong Kong, Hong Kong, China) Edge pricing of multicommodity networks for selfish users with elastic demands George Karakostas (McMaster University) Stavros Kolliopoulos (University of Athens) Aggregating Strategy for Online Auctions Eiji Takimoto (Tohoku University) Shigeaki Harada (Tohoku University) Akira Maruoka (Tohoku University) 10:20 am - 12:00 noon: Session B Graph Algorithms and Applications Session Chair: Tsan-sheng Hsu Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants Stefan Richter (RWTH Aachen University) Peter Rossmanith (RWTH Aachen University) Daniel Moelle (RWTH Aachen University) A Detachment Algorithm for Inferring a Graph from Path Frequency Hiroshi Nagamochi (Kyoto University) The d-Identifying Codes Problem for Vertex Identification in Graphs: Probabilistic Analysis and an Approximation Algorithm Ying Xiao (University of Oklahoma) Christoforos Hadjicostis (University of Illinois at Urbana-Champaign) Krishnaiyan Thulasiraman (University of Oklahoma) Reconstructing Evolution of Natural Languages: Complexity and Parameterized Algorithms Iyad A Kanj (DePaul University) Luay Nakhleh (Rice University) Ge Xia (Lafayette College) 12:00 - 1:30 pm: Lunch 1:30 - 3:10 pm: Session A Graph Algorithms Session Chair: Siu-Wing Cheng On Indecomposability Preserving Elimination Sequences Chandan K. Dubey (Indian Institute of Technology, Kanpur) Shashank Kantilal Mehta (Indian Institute of Technology. Kanpur) Improved Algorithms for the Minmax Regret 1-Median Problem Biing-Feng Wang (National Tsing Hua University) Tzu-Chin Lin (National Tsing Hua University) Hung-I Yu (National Tsing Hua University) Partitioning a Multi-Weighted Graph to Connected Subgraphs of Almost Uniform Size Takehiro Ito (Tohoku University) Kazuya Goto (Tohoku University) Xiao Zhou (Tohoku University) Takao Nishizeki (Tohoku University) Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs Min Chih Lin (Universidad de Buenos Aires - Facultad de Cs. Exactas y Naturales) Jayme Luiz Szwarcfiter (Universidade Federal do Rio de Janeiro) 1:30 - 3:10 pm: Session B On-line Algorithms Session Chair: Rudolf Fleicher On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis Wun-Tat Chan (University of Hong Kong) Prudence W.H. Wong (The University of Liverpool) Fencol Yung (The University of Hong Kong) Improved on-line broadcast scheduling with deadlines Stanley P Y Fung (University of Leicester) Feifeng Zheng (Xi'an JiaoTong University, China) Wun-Tat Chan (University of Hong Kong) Francis Chin (The University of Hong Kong) Chung Keung Poon (City University of Hong Kong) Prudence W.H. Wong (The University of Liverpool) A Tight Analysis of Most-Requested-First for On-demand Data Broadcast Yee Shing Regant Hung (Department of Computer Science, The University of Hong Kong) Hing Fung Ting (The University of Hong Kong) On Lazy Bin Covering and Packing Problems Mingen Lin (University at Buffalo, the State University of New York) Yang Yang (University at Buffalo, the State University of New York) Jinhui Xu (University at Buffalo, the State University of New York) 3:10 - 3:30 pm: Break 3:30 - 4:45 pm: Session A Computational Complexity and Computability Session Chair: Da-Wei Wang Varieties Generated by Certain Models of Reversible Finite Automata Marats Golovkins (University of Latvia) Jean-Éric Pin (Université Paris VII and CNRS) Iterated TGR languages: Membership problem and effective closure properties Kai Salomaa (Queen's University) Ian McQuillan (University of Saskatchewan) Mark Daley (University of Western Ontario) On the Negation-Limited Circuit Complexity of Sorting and Inverting K-tonic Sequences Kazuyuki Amano (Tohoku University) Takayuki Sato (Sendai National Colledge of Technology) Akira Maruoka (Tohoku University) 3:30 - 4:45 pm: Session B Graph Theory Session Chair: Peter Widmayer Creation and growth of components in a random hypergraph process Vlady Ravelomanana (Institut Galilée -- University of Paris Nord) Optimal acyclic edge colouring of grid like graphs Narayanan Narayanan (Institute of Mathematical Sciences) Rahul Muthu (Institute of Mathematical Sciences) Chinthamani R Subramanian (Institute of Mathematical Sciences) An Edge Ordering Problem of Regular Hypergraphs Hongbing Fan (Wilfrid Laurier University) Robert Kalbfleisch (Wilfrid Laurier University) 4:50 - 5:40 pm: Session A Quantum Computing Session Chair: Naoki Katoh Robust quantum algorithms with $\epsilon$-biased oracles Tomoya Suzuki (Nara Institute of Science and Technology) Shigeru Yamashita (Nara Institute of Science and Technology) Katsumasa Watanabe (Nara Institute of Science and Technology) Masaki Nakanishi (Nara Institute of Science and Technology) The Complexity of Black-Box Ring Problems Vikraman Arvind (Institute of Mathematical Sciences, Chennai, India) Bireswar Das (Institute of Mathematical Sciences, Chennai) Partha Mukhopadhyay (Institute of Mathematical Sciences, Chennai) 4:50 - 5:40 pm: Session B Algorithms for Security and Systems Session Chair: Chi-Jen Lu Efficient Partially Blind Signature Scheme with Provable Security Gong Zheng (Shanghai Jiaotong University) Xiangxue Li (Shanghai Jiaotong University) Kefei Chen (Shanghai Jiaotong University) A rigorous analysis for set-up time models - a metric perspective Eitan Bachmat (Ben Gurion University) Tao Kai Lam (EMC Corporation) Avner Magen (university of toronto) August 17, Thursday 9:00 - 10:15 am: Session A Computational Biology and Medicine Session Chair: Francis Chin Lower Bounds and Parameterized Approach for Longest Common Subsequence Xiuzhen Huang (Arkansas State University) Finding Patterns with Variable Length Gaps or Don't Cares Mohammad Sohel Rahman (King's College London) Costas Iliopoulos (King's College London) Inbok Lee (Seoul National University) Manal Mohamed (King's College London) William F. Smyth (McMaster University) The Matrix Orthogonal Decomposition Problem in Intensity-Modulated Radiation Therapy Xiaodong Wu (The University of Iowa) Xin Dou (The University of Iowa) John E Bayouth (The University of Iowa) John M Buatti (The University of Iowa) 9:00 - 10:15: Session B Discrete Geometry and Graph Theory Session Chair: Jinhui Xu Geometric representation of graphs in low dimension L. Sunil Chandran (Indian Institute of Science) Naveen Sivadasan (Strand Life Sciences) The On-Line Heilbronn's Triangle Problem in $d$ Dimensions Gill Barequet (Technion---Israel Inst. of Technology) Alina Shaikhet (Technion---Israel Inst. of Technology) Counting d-Dimensional Polycubes and Nonrectangular Planar Polyominoes Gill Barequet (Technion---Israel Inst. of Technology) Gadi Aleksandrowicz (Technion---Israel Inst. of Technology) 10:15 am - 7:00 pm: Excursion 7:00 pm: Banquet August 18, Friday 9:00 - 10:00 am: Invited Talk (Moderator: Danny Z. Chen) Security Issues in Collaborative Computing Mikhail J. Atallah (Purdue University, USA) 10:00 - 10:20 am: Break 10:20 am - 12:00 noon: Session A Computational Geometry Session Chair: Rolf Klein A polynomial-time approximation algorithm for a geometric dispersion problem Joachim Gudmundsson (National ICT Australia Ltd) Marc Benkert (Karlsruhe University) Rene van Oostrum (Utrecht University) Christian Knauer (Freie University, Berlin) Alexander Wolff (Karlsruhe University) Esther Moet (Utrecht University) A PTAS for cutting out polygons with lines Minghui Jiang (Utah State University) Sergey Bereg (University of Texas at Dallas) Ovidiu Daescu (University of Texas at Dallas) On Unfolding Lattice Polygons and Trees + Straightening 2D Trees of Diameter 4 Sheung-Hung Poon (TU Eindhoven) Restricted Mesh Simplification using Edge Contractions Mattias Hans Andersson (Lund University) Christos Levcopoulos (Lund University) Joachim Gudmundsson (National ICT Australia) 10:20 am - 12:00 noon: Session B Approximation Algorithms Session Chair: Peter Bro Miltersen Approximating min-max (regret) versions of some polynomial problems Cristina Bazgan (University Paris Dauphine) Hassene Aissi (University Paris Dauphine) Daniel Vanderpooten (University Paris Dauphine)   The class constrained bin packing problem with applications to video-on-demand Flavio Miyazawa (State University of Campinas- (Unicamp)) Eduardo Candido Xavier (State University of Campinas- (Unicamp)) MAX-SNP Hardness and Approximation of Selected-Internal Steiner Trees Sun-Yuan Hsieh (National Cheng Kung University) Minimum Clique Partition Problem with Constrained Weight for Interval Graphs Jianping Li (Yunnan University) Jianbo Li (Kunming University of Science and Technology) Weidong Li (Yunnan University) 12:00 - 1:30 pm: Lunch 1:30 - 2:45 pm: Session A Graph Theory Session Chair: Ming-Tat Ko Enumerating Non-crossing Minimally Rigid Frameworks Naoki Katoh (Kyoto University) David Avis (McGill University) Makoto Ohsaki (Kyoto University) Ileana Streinu (Smith College) Shin-ichi Tanigawa (Kyoto University) k-tree characterizing sequences N.S. Narayanaswamy (I.I.T Madras) Lotker Zvi (CWI) Ingmar Weber (MPI) Debapriyo Majumdar (MPI) On the Threshold of Having a Linear Treewidth in Random Graphs Yong Gao (University of British Columbia Okanagan)  1:30 - 2:45 pm: Session B Computational Complexity and Computability Session Chair: Xiaotie Deng Overlap-Free Regular Languages Yo-Sub Han (Korea Institute of Science and Technology) On the Combinatorial Representation of Information Joel Ratsaby (Ben Gurion University of the Negev) Finding small OBDDs for incompletely specified truth tables is hard Peter Bro Miltersen (University of Aarhus) Jesper Torp Kristensen (University of Aarhus) 2:45 - 3:05 pm: Break 3:05 - 4:20 pm: Session A Computational Biology Session Chair: Louxin Zhang Reconciling Gene Trees with Apparent Polytomies Wen-Chieh Chang (Iowa State University) Oliver Eulenstein (Iowa State University) Lower Bounds on the Approximation of the Exemplar Conserved Interval Distance Problem of Genomes Zhixiang Chen (University of Texas - Pan American) Richard H Fowler (University of Texas - Pan American) Bin Fu (University of New Orleans) Binhai Zhu (Montana State University) Computing Maximum-Scoring Segments in Almost Linear Time Fredrik Bengtsson (Luleå University of Technology) Jingsen Chen (Luleå University of Technology) 3:05 - 4:20 pm: Session B Experimental Algorithms Session Chair: Churn-Jung Liau Bimodal Crossing Minimization Merijam Percan (University of Cologne) Christoph Buchheim (University of Cologne) Michael Jünger (University of Cologne) Annette Menze (University of Cologne)   Fixed linear crossing minimization by reduction to the maximum cut problem Lanbo Zheng (University of Sydney) Christoph Buchheim (University of Cologne) Effectiveness of the Linear Programming Relaxation of the 0-1 Multi-commodity Minimum Cost Network Flow Problem Dae-Sik Choi (Korea University) In-chan Choi (Korea University) End of Conference