From dmanet@math.utwente.nl Mon May 31 04:46:41 1999 Date: Mon, 31 May 1999 11:50:19 +0200 From: Discrete Mathematics and Algorithms Network Reply-To: nakano@msc.cs.gunma-u.ac.jp To: DMA-LIST@NIC.SURFNET.NL Subject: COCOON99(July 26-28, Tokyo) Call for Participation COCOON'99 Fifth Annual International Computing and Combinatorics Conference July 26-28, 1999, Tokyo, Japan http://www.ecei.tohoku.ac.jp/COCOON99 ------------------------------------------------------------------------ Reminder: Early registration ends on June 10. COCOON'99 Registration Server at http://cocoon.is.s.u-tokyo.ac.jp/index.html ------------------------------------------------------------------------ Topics - algorithms and data structures - automata, languages and logic - complexity and computability - computational biology and chemistry - computational geometry and algebra - cryptography and computational number theory - learning theory and knowledge discovery - optimization and network theory - parallel and distributed computing - graph drawing and information visualization - combinatorics related to algorithms and complexity ------------------------------------------------------------------------ PRELIMINARY PROGRAM %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Evening, July 25 Welcome Reception %---------------- Morning July 26 Session 1. Invited Talk 1: "The Web As a Graph: Measurements, Models and Methods" Prabhakar Raghavan (IBM Almaden Research Center) %---------------- Session 2-A. Data Structures: "Theory of 2-3 heaps" Tadao Takaoka (University of Canterbury) "An External Memory Data Structure for Shortest Path Queries" David Hutchinson, Anil Maheshwari (Carleton University), and Norbert Zeh (Carleton University and Friedrich-Schiller-Universit\"{a}t) %----------------- Session 2-B. Computational Biology: "Approximating the Nearest Neighbor Interchange Distance for Evolutionary Trees with Non-Uniform Degrees" Wing-Kai Hon and Tak-Wak Lam (University of Hong Kong) "Signed Genome Rearrangement by Reversals and Transpositions: Models and Approximations" Guo-Hui Lin and Guoliang Xue (University of Vermont) %-------------- Afternoon, July 26: Session 3. Hao Wang Award Paper Presentation: "An Approximation for Finding a Smallest 2-Edge-Connected Subgraph Containing a Specified Spanning Tree" Hiroshi Nagamochi, Toshihide Ibaraki (Kyoto University) %----------------------------------------- Section 4-A. Graph Drawing: "An Approximation Algorithm for the Two-layered Graph Drawing Problem" Atsuko Yamaguchi and Akihiro Sugimoto (Hitachi Advanced Research Laboratory) "Area Minimization for Grid Visibility Representation of Hierarchically Planar Graphs" Xuemin Lin (University of New South Wales) and Peter Eades (University of Newcastle) "Layout Problems on Lattice Graphs" Josep D\'{\i}az (Universitat Polit\`{e}cnica de Catahinya) , Mathew D. Penrose (University of Durham) , Jordi Petit, and Mar\'{\i}a Serna (Universitat Polit\`{e}cnica de Catahinya) %---------------------------------------- Section 4-B. Discrete Mathematics : "A New Transference Theorem in the Geometry of Numbers" Jin-Yi Cai (SUNY Buffalo) "On Covering and Rank Problems for Matrices and Their Applications" Carsten Damm (Universit\"{a}t Trier), Ki Hang Kim, and Fred Roush (Alabama State University) "A Combinatorial Algorithm for Pfaffian" Meena Mahajan (Institute of Mathematical Sciences), P. R. Subramanya, and V. Vinay (Indian Institute of Science) %----------------------------------------- Session 5-A. Graph Algorithm 1: "How to Swap a Failing Edge of a Single Source Shortest Paths Tree" Enrico Nardelli, Guido Proietti, (Universit\`{a} di L'Aquila) and Peter Widmayer (ETH Zentrum) "On Bound for the k-Partitioning of Graphs" S. L. Bezrukov (University of Wisconsin), R. Elsaesser, and U.-P. Schroeder (University of Paderborn) "A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts" Hiroshi Nagamochi, Shigeki Katayama, Toshihide Ibaraki (Kyoto University) %----------------------------------------- Session 5-B. Automata and Language: "Probabilities to Accept Languages by Quantum Finite Automata" Andris Ambanis (UC Berkeley), Richard Bonner (M\"{a}lardalens University), Rusins Freivalds, and Arnolds Kikusts (University of Latvia) "Distributionally-Hard Languages" Lance Fortnow (University of Chicago), A. Pavan, and Alan L. Selman (University at Buffalo) "Circuits and Context-free Languages" Pierre McKenzie(Universit\'{e} de Montr\'{e}al), Klaus Reinhardt(Universit\"{a}t T\"{u}bingen), and V. Vinay(Indian Institute of Science) %----------------------------------------- Evening, July 26 Special Session: Tokyo Excursion %----------------------------------------- %-------------------------- Morning July 27: Session 6: Invited Talk 2: "Some Observations on the Complexity of Graph Accessibility Problem", Seinosuke Toda (Nihon University) %----------------------------------------- Session 7-A. Complexity Theory: "On the Negation Limited Circuit Complexity of Merging" Kazuyuki Amano, Akira Maruoka (Tohoku University), and Jun Tarui(University of Electro-Communications) "Super-polynomial Versus Half-exponential Circuit Size in the Exponential Hierarchy" Peter Bro Miltersen (University of Aarhus), N. V. Vinodchandran (Institute of Mathematical Science), and Osamu Watanabe (Tokyo Institute of Technology) "Efficient Learning of Some Linear Matrix Languages" Henning Fernau (Universit\"{a}t T\"{u}bingen) %----------------------------------------- Session 7-B. Combinatorial Optimization 1: "Minimizing Mean Response Time in Batch Processing System" Xiaotie Deng (City University of Hong Kong) and Yuzhong Zhang (Qufu Normal University) "Approximation Algorithms for Bounded Facility Location" Piotr Krysta and Roberto Solis-Oba (Max-Planck-Instutut f\"{u}r Informatik) "Scheduling Trees onto Hypercubes and Grids Is NP Complete" Satoshi Tayu (Japan Advanced Institute of Science and Technology) %----------------------------------------- Afternoon, July 27, %----------------------------------------- Session 8-A. Graph Algorithm 2: "Approximations of Independent Set Variants and Hereditary Subset" Magn\'{u}s M. Halld\'{o}rsson (University of Iceland) "Multi coloring trees" Magn\'{u}s M. Halld\'{o}rsson (University of Iceland), Guy Kortsarz (Open University), Andrzej Proskurowski (University of Oregon), Ravit Salman, Hadas Shachnai (Technion), Jan Arne Teller (University of Bergen) "On the Complexity of Approximating Colored-Graph Problems" Andrea E. F. Clementi (Universit\`{a} degli Studi di Roma Tor Vergata), Pierluigi Cresenzi (Universit\`{a} degli Studi di Furenze), and Gianluca Rossi (Universit\`{a} degli Studi di Roma La Sapienza) %----------------------------------------- Session 8-B. Number Theory: "On the Average Sensitivity of Testing Square-Free Numbers" Anna Bernasconi (Technische Universit\"{a}t M\"{u}nchen) , Carsten Damm (Universit\"{a}t Trier) and Igor Shparlinski (Macquarie University) "Binary Enumerablility of Real Numbers" Xizhong Zheng (Fern Universit\"{a}t Hagen) "GCD of Many Integers" Gene Cooperman (Northeastern University), Sandra Feisel, Joachim von zur Gathen (Universit\"{a}t-GH Paderborn), George Havas (University of Queensland) Sesion 9-A. Distributed computing: "Multi-party Finite Computations" Tomasz Jurdzinski (Wroclaw University), Miroslaw Kutylowski (Wroclaw University and Pozna\{`}n University), and Krzysztof Lorys (Woclaw University) " Probalilistic Local Majority Voting for the Agreement Problem on Finite Graphs" Toshio Nakata (Fukuoka University of Education), Hiroshi Imahayashi, and Masafumi Yamashita (Kyushu University) Session 9-B. Combinatorial Optimization 2: "A Dynamic Programming Bound for the Quadratic Assignment Problem" Ambros Marzetta (International Computer Science Institute, Berkeley) and Adrian Br\"{u}ngger (Novartis Pharma AG) "A New Approach for Speeding Up Enumeration Algoirthms and Its Application for Matroid Bases" Takeaki Uno (Tokyo Institute of Technology) %------------------------------- Session 10-A. Network Routing Problems: "On Routing in Circulant Graphs" Jin-Yi Cai (SUNY Buffalo), George Havas(University of Queensland), Bernard Mans(Macquarie University) , Ajai Nerurkar (SUNY Buffalo), Jean-Pierre Seifert(University of Frankfurt), Igor Shparlinski (Macquarie University) "Minimum Congestion Embedding of Complete Binary Trees into Tori" Akira Matsubayashi and Ryo Takasu (Utsunomiya University) %----------------------------------- Session 10-B. Computational Geometry: "Maximum Stabbing Line in 2D Plane" Francis Y. L. Chin (University of Hong Kong), Cao An Wang (Memorial University of Newfoundland), and Fu Lee Wang (University of Hong Kong) "Generalized Shooter Location Problem" Jeet Chaudhri and Subhash C. Nandy (Indian Statistical Institute) %----------------------------------- Evening, July 27 Conference Banquet (hosted by Chuo University President) %------------------------------- %------------------------------- Morning, July 28 %----------------------- Session 11-A. Online Algorithms: "A Competitive Online Algorithm for the Paging Problem with ``Shelf'' Memory" Sung-Pil Hong (Chung-Ang University) "Using Generalized Forecasts for Online Currency Conversion" Kazuo Iwama and Kouki Yonezawa (Kyoto University) %-------------------------- Session 11-B. Rewriting systems: "On S-regular Prefix-rewriting Systems and Automatic Structures" Friedrich Otto (Universit\"{a}t Kassel) "Tractable and Intractable Second-Order Matching Problems" Kouichi Hirata, Keizo Yamada, and Masatetsu Harao (Kyushu Institute of Technology) %--------------------- Section 12-A. Parallel computing: "Design and Analysis of Fixed-size Systolic Arrays for the Modular Multiplication" Hyun-Sung Kim, Sung-Woo Lee (Kyungpook National University), Jung-Joon Kim, Tae-Geun Kim (Wireless Comm. Research Laboratory) and Kee-Young Yoo (Kyunpook National University) "Improving Parallel Computation with Fast Integer Sorting" Ka Wong Chong (University of Hong Kong), Yijie Han (Electronic Data System), Yoshihide Igarashi (Gunma University), and Tak Wak Lam (University of Hong Kong) "A Combinatorial Approach to Performance Analysis of a Multiprocessor System" Sajal K. Das (University of Texas), Bhabani P. Sinha, Rajarshi Chaudhuri (Indian Statistical Institute) %------------------------------------------------ Session 12-B. Combinatorial Optimzation 3: "A Fast Approximation Algorithm for TSP with Neighborhoods and Red-Blue Separation" Joachim Gudmundsson and Christos Levcopoulos (Lund University) "The Greedier the Better: An Efficient Algorithm for Approximating Maximum Independent Set" H. Y. Lau and H. F. Ting (University of Hong Kong) %------------------------------------------------ Afternoon, July 28 Specially Organized Session (this session is open to the public) "Introduction to LEDA, Library of Efficient Data Types and Algorithms (tentative)" Kurt Mehlhorn (Max-Planck-Institut f\"{u}r Informatik) ****************************************************** Contributions to be spread via DMANET are submitted to DMANET@math.utwente.nl Replies to a message carried on DMANET should NOT be addressed to DMANET but to the original sender. The original sender, however, is invited to prepare an update of the replies received and to communicate it via DMANET. DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET) http://www.math.utwente.nl/stor/OR/dmanet.html