From - Sun Nov 2 21:31:09 1997 Received: from CS.Stanford.EDU (CS.Stanford.EDU [171.64.64.64]) by robotics.Stanford.EDU (8.8.7/8.8.7) with ESMTP id JAA17506; Mon, 6 Oct 1997 09:27:15 -0700 (PDT) Received: from hearnnt.nic.surfnet.nl (hearnnt.nic.surfnet.nl [192.87.5.133]) by CS.Stanford.EDU (8.8.7/8.8.7) with ESMTP id IAA10246; Mon, 6 Oct 1997 08:03:46 -0700 (PDT) Received: from hearnnt (192.87.5.133) by hearnnt.nic.surfnet.nl (LSMTP for Windows NT v1.1a) with SMTP id <0.20AF81E0@hearnnt.nic.surfnet.nl>; Mon, 6 Oct 1997 16:58:54 +0200 Received: from NIC.SURFNET.NL by NIC.SURFNET.NL (LISTSERV release 1.8c) with NJE id 5642 for DMA-LIST@NIC.SURFNET.NL; Mon, 6 Oct 1997 17:03:56 +0200 Received: from HEARN (NJE origin SMTP@HEARN) by HEARN.NIC.SURFNET.NL (LMail V1.2c/1.8c) with BSMTP id 5352; Mon, 6 Oct 1997 17:03:55 +0200 Received: from utmfu6.math.utwente.nl by HEARN.nic.SURFnet.nl (IBM VM SMTP V2R2) with TCP; Mon, 06 Oct 97 17:03:51 +0200 Received: from utmfu0.math.utwente.nl (utmou1.math.utwente.nl) by utmfu6.math.utwente.nl with ESMTP (1.40.112.8/16.2) id AA278310166; Mon, 6 Oct 1997 17:02:48 +0200 Received: by utmfu0.math.utwente.nl ($Revision: 1.36.108.11 $/16.2) id AA020720164; Mon, 6 Oct 1997 17:02:44 +0200 Mailer: Elm [revision: 66.36.1.1] Approved-By: DMANET Message-ID: <199710061502.AA020720164@utmfu0.math.utwente.nl> Date: Mon, 6 Oct 1997 17:02:43 METDST Reply-To: lhui@iscs.nus.edu.sg Sender: DMANET From: DMANET Subject: ISAAC'97 Prelim Call for Participation To: DMA-LIST@NIC.SURFNET.NL X-Mozilla-Status: 8001 Status: O X-Status: ISAAC97 Preliminary Call For Participation Eight Annual International Symposium on Algorithms and Computation Merchant Court Hotel Singapore December 17-19, 1997 Organized by Department of Information Systems & Computer Science National University of Singapore Overview The symposium will provide a forum for researchers working in algorithms and the theory of computation. Papers presenting original research in the areas of design and analysis of algorithms, computational complexity, and theory of computation will be presented. Details of the conference can also be found in the world wide web sites http://www.iscs.nus.sg/~isaac97/isaac97.html and http://naomi.is.s.u-tokyo.ac.jp/isaac97.html. Symposium Site ISAAC97 will be held in the Merchant Court Hotel at Merchant Road, Singapore. Merchant Court Hotel is a new hotel located in the heart of the city, along the banks of Singapore River and next to the financial and business district. It is within easy walking distance to Singapore's prime shopping, dining and entertainment areas like Clarke Quay Festival Village and Boat Quay. More information about the hotel can be found in the world wide web site http://www.raffles.com/ril. Tourist information about Singapore can be found in the world wide web site http://www.sg. The average temperature in Singapore in December is 30C or 86F. Organizing Committee Chair : Hon Wai Leong Publicity : Lucas Chi Kwong Hui Local Arrangement : Kwok-Yan Lam Treasurer : Tiow Seng Tan Publication : Sanjay Jain Exhibition : Hong Gian Chew Conference Secretary : Mary Lau Symposium Chair : Hon Wai Leong (Nat. U. Spore) Program Committee H. Imai (Co-Chair; U. Tokyo, Japan) H. W. Leong (Co-Chair; Nat. U. Spore) K. Y. Chwa (KAIST, Korea) P. Eades (U. Newcastle, Australia) H. Edelsbrunner (U. Illinois, USA) D. Eppstein (UC Irvine, USA) A. Gibbons (U. Liverpool, UK) L. C. K. Hui (Nat. U. Spore, Singapore) S. Jain (Nat. U. Spore, Singapore) K. Kobayashi (TIT, Japan) M. Li (City U., Hong Kong; P. Rangan (IIT-Madras, India) U. Waterloo, Canada) F. Ruskey (U. Victoria, Canada) H. Suzuki (U. Ibaraki, Japan) C. Y. Tang (Nat. Tsing Hua U., Taiwan) Conference Office ISAAC97 Mary Lau Department of Information Systems & Computer Science National University of Singapore Kent Ridge, S(119260) Republic of Singapore Did : (65) 8745242 Fax : (65) 7794580 isaac97@iscs.nus.edu.sg Registration Mail or fax completed registration forms to the Conference Office with payment in full. Registration must be in Singapore Dollars. Fees will be returned in full for any written cancellation recieved on or before 15 Nov 1997. Early Registration : (on or before 15 November 1997) Full fee: $560 Student: $200 Late Registration : (after 15 November 1997) add $150 to the above fee. The Conference registration fee includes: * conference participation * the conference banquet (not applicable to student registration) * a copy of the proceedings * conference lunch * morning and afternoon tea * the welcome cocktail reception on Tuesday 16 December, 1997 (not applicable to student registration) Proceedings Springer-Verlag will publish the conference proceedings. The working language of the conference will be English, which will be used for all printed material, presentation and discussions. Extra proceedings can be purchased at the conference site. Passports Participants are advised to check their individual circumstances for entry into Singapore. Citizens of some countries may need to arrange a visa through a travel agent or their local Singapore Consulate. Transport The Merchant Court Hotel is approximately 15 kilometers from the international airport in Singapore. Taxi fare in Singapore is affordable when compared to most other countries. The MRT (Mass Rapid Transit) is an efficient and convenient public transport in Singapore. There are complimentary shuttle bus between Merchant Court Hotel and the City Hall MRT station between 0800 and 2345 hours. Financial Transactions The local unit is the Singapore Dollar. Most hotels, restaurants and shops will accept major international credit cards. Banks are open from Monday to Saturday. The exchange rate of Singapore dollar is roughly 1 US dollar = 1.5 Singapore dollar. Time Singapore local time is in the +8 (GMT) time zone and so will be 13 hours ahead of North American Eastern Standard time and 1 hour behind Japanese time. Accommodation Merchant Court hotel is holding blocks of rooms for ISAAC97 participants. All reservations must be made DIRECTLY to the hotel. In order to obtain the special discount rate for ISAAC97, mention the conference in your correspondence. ADVANCE PROGRAMME for ISAAC-97 ============================== DAY 1: 17th DECEMBER 1997 (WED) ------------------------------------------------------------ 8:30am REGISTRATION ------------------------------------------------------------ 9:00am OPENING REMARKS 9:30am KEYNOTE TALK : Prof. T. Ibaraki Solving NP-hard combinatorial problems in the practical sense ------------------------------------------------------------ 10:30am BREAK ------------------------------------------------------------ 11:00am SESSION 1: Transportation and Logistics (3 Papers) Airline crew scheduling problem with many irregular flights Akira Tajima and Shinji Misono Practical approach to a facility location problem for Large-Scale Logistics Kazuyoshi Hidaka and Hiroyuki Okano Hard instance generation for SAT Satoshi Horie and Osamu Watanabe ------------------------------------------------------------ 12:30pm LUNCH ------------------------------------------------------------ 2:00pm SESSION 2A: Combinatorial Alg. 1 (3 papers) Playing tetris on meshes and multi-dimensional SHEARSORT Miroslaw Kutylowski and Rolf Wanka Formulation of the addition-shift-sequence problem and its complexity Akihiro Matsuura and Akira Nagoya Weighted and unweighted selection algorithms for k sorted sequences Tatsuya Hayashi, Koji Nakano and Stephan Olariu ------------------------------------------------------------ 2:00pm SESSION 2B: (in parallel with 2A) Network Routing Algorithms (3 papers) An adaptive distributed fault-tolerant routing algorithm for the star graph Leqiang Bai, H. Ebara, Hideo Nakano and Hajime Maeda Multi-color routing in the undirected hypercube Qian-Ping Gu and Hisao Tamaki Competitive source routing on tori and meshes Tzuoo-Hawn Yeh, Cheng-Ming Kuo, Chin-Luang Lei and Hsu-Chun Yen ------------------------------------------------------------ 3:30pm BREAK ------------------------------------------------------------ 4:00pm SESSION 3A: Graph Algorithms (2 papers) Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs Takeaki Uno Augmenting edge and vertex connectivities simultaneously Toshimasa Ishii, Hiroshi Nagamochi and Toshihide Ibaraki ------------------------------------------------------------ 4:00pm SESSION 3B: Logic: Horn Extension (2 papers) Two-face Horn extensions Thomas Eiter, Toshihide Ibaraki and Kazuhisa Makino Decremental maintenance of reachability in hypergraphs and minimum models of Horn formulae Giorgio Ausiello, Paolo Giulio Franciosa, Daniele Frigioni and Roberto Giaccio ------------------------------------------------------------ 5:00pm END OF TECHNICAL SESSIONS (DAY 1) DAY 2: 18th DECEMBER 1997 (THU) ------------------------------------------------------------ 9:00am KEYNOTE TALK 2: Prof. C. E. Leiserson, MIT Analysis of multithreaded algorithms 10:00am BEST PAPER PRESENTATION A characterization of planar graphs by pseudo-line arrangements Hisao Tamaki and Takeshi Tokuyama ------------------------------------------------------------ 10:30am BREAK ------------------------------------------------------------ 11:00am SESSION 4A: Combinatorial Alg 2 (3 papers) Optimal fault-tolerant broadcasting in trees Petrisor Panaite and Andrzej Pelc A theoretical framework of hybrid approaches to MAX SAT Takao Asano, Kuniaki Hori, Takao Ono and Tomio Hirata Exponential lower bounds on the size of OBDDs representing integer division Takashi Horiyama and Shuzo Yajima ------------------------------------------------------------ 11:00am SESSION 4B: Protocols (3 papers) On-line versus off-line in money-making strategies with brokerage Eisuke Dannoura Kouichi Sakurai Decision-making by hierarchies of discordant agents XiaoTie Deng and Christos Papadimitriou A new efficient off-line anonymous cash scheme Khanh Quoc Nguyen, Vijay Varadharajan and Yi Mu ------------------------------------------------------------ 12:30pm LUNCH ------------------------------------------------------------ 2:00pm SESSION 5A: Parallel Graph Alg. (3 papers) Approximating unweighted connectivity problems in parallel Zhi-Zhong Chen A randomized linear work EREW PRAM algorithm to find a minimum spanning forest Chung Keung Poon and Vijaya Ramachandran Efficient parallel algorithms for planar st-graphs Mikhail J. Atallah, Danny Z. Chen and Ovidiu Daescu ------------------------------------------------------------ 2:00pm SESSION 5B: Computational Learning (3 papers) Peg-solitaire, string rewriting systems and finite automata B. Ravikumar On the size of probabilistic formulae Hartmut Klauck Homophonic coding with logarithmic memory size Boris Ryabko and Andrey Fionov ------------------------------------------------------------ 3:30pm BREAK ------------------------------------------------------------ 4:00pm SESSION 6A: Computational Geometry (2 papers) Complexity and modeling aspects of mesh refinement into quadrilaterals Rolf H. Mohring and Matthias Muller-Hannemann Topology oriented vs exact arithmetic -- experience in implementing the three-dimensional convex hull algorithm Tsuyoshi Minakawa and Kokichi Sugihara ------------------------------------------------------------ 4:00pm SESSION 6B: Database Query Processing The complexity of learning branches and strategies from queries Matthias Ott and Frank Stephan Singularities make spatial join scheduling hard Gabriele Neyer and Peter Widmayer ------------------------------------------------------------ 5:00pm END OF TECHNICAL SESSIONS (DAY 2) CONFERENCE BANQUET ------------------------------------------------------------ DAY 3: 19th DECEMBER 1997 (FRI) ------------------------------------------------------------- 9:00am SESSION 7A: VLSI Algorithms (3 papers) A faster one-dimensional topological compaction algorithm Hsiao-Feng Steven Chen and D. T. Lee Algorithms for finding optimal disjoint paths around a rectangle Wun-Tat Chan and Francis Y.L. Chin An algorithm for finding a region with the minimum total L_1 distance from prescibed terminals Yoshiyuki Kusakari and Takao Nishizeki ------------------------------------------------------------ 9:00am SESSION 7B: Problems in Graph (3 papers) On defect sets in bipartite graphs P.E.Haxell and M.Loebl Dynamic programming on distance-hereditary graphs Maw-Shang Chang, Sun-Yuan Hsieh and Gen-Huey Chen On the equivalence in complexity among basic problems on bipartite and parity graphs Serafino Cicerone and Gabriele Di Stefano ------------------------------------------------------------ 10:30am BREAK ------------------------------------------------------------ 11:00am SESSION 8A: Computational Geometry 2 (3 papers) All-cavity maximum matchings Ming-Yang Kao, Tak Wah Lam, Wing Kin Sung and Hing Fung Ting Fast algorithms for computing \beta-skeletons and their relatives S. V. Rao and Asish Mukhopadhyay A branch-and-cut approach for minimum weight triangulation Yoshiaki Kyoda, Keiko Imai, Fumihiko Takeuchi and Akira Tajima ------------------------------------------------------------ 11:00am SESSION 8B: Approximation Alg (3 papers) An efficient approximation scheme for the subset-sum problem Hans Kellerer, Ulrich Pferschy and Maria Grazia Speranza Competitive call control in mobile networks Grammati E. Pantziou, George Pentaris and Paul Spirakis Generalized swap-with-parent schemes for self-organizing sequential linear lists John Oommen and Juan Dong ------------------------------------------------------------ 12:30pm LUNCH ------------------------------------------------------------ 2:00pm Some Tours to university/research-institutes/industry/etc/ -- to be arranged ------------------------------------------------------------ 5:00pm END OF SYMPOSIUM ---------------------------------------------------------------------------- ISAAC97 Conference Registration (All in Singapore dollar) Exchange rate: 1 US dollar = 1.5 Singaporean dollar Early Registration : (on or before 15 November 1997) Full fee: $560 Student: $200 Late Registration : (after 15 November 1997) add $150 to the above fee. All payments must be made in Singapore Dollars using cheque, money order made payable to "National University of Singapore", or by credit card (VISA or MasterCard). Confirmation will be mailed upon receipt of registration fee. Name: Affiliation: Address: Phone: Fax: Email: Name Badge Preference: Regular registration fee: Student registration fee: Total Amount Enclosed: Payment method: Check / Money Order / Visa / MasterCard Credit card information Card number: Expiry Date: Amount charged: Signature: Please mail/fax information to : ISAAC97 - Registration Mary Lau Department of Information Systems & Computer Science National University of Singapore Kent Ridge, S(119260) Republic of Singapore Did : (65) 8745242 Fax : (65) 7794580 isaac97@iscs.nus.edu.sg ---------------------------------------------------------------------------- ---------------------------------------------------------------------------- Room Reservation Form ISAAC 1997 Conference (17-19 Dec 1997) Merchant Court Hotel 20 Merchant Road S(058281) Singapore mchotel@singnet.com.sg To : Ms Karen Lee (Reservation Manager) - Merchant Court Hotel Fax : (65) 336 9993 Tel : (65) 337 2288 Rate(S$) Category Single Twin Superior $149 $149 Deluxe $169 $169 *Merchant Club Room $192 $210 *Merchant Club rooms are inclusive of two pieces of free pressing upon arrival. Guests are also entitled to complementary continental breakfast and evening cocktails at The Merchant Club Lounge as well as unlimited free local telephone calls. Above rates quoted are subject to 10% service charge, cess (currently 1 %) and goods and services tax (currently 3%). These rates are computed at a total of 14.33%. Name: _____________________________________ Passport No : ______________ Address : ______________________________________________________________ Country : _________________ Tel No : _____________ Fax No: _____________ Check in Date : __________________ Check out Date : ____________________ Arrival Flight No : ______________ Departure Flight No : _______________ Credit Card No : _______________________ Expiry Date: __________________ Type : ___ AmEx ___ Visa ___ JCB ___ Master ___ Diner Occupancy : ___ Single ___ Twin Room Type : ___ Superior ___ Deluxe ___ Merchant Club Room Cancellation Policy : Any cancellation received less than 72 hours prior to arrival will be charged a fee equal to one night's room rate plus applicable taxes and service charge. Tha same fee applies to no-shows on the day of arrival. _____________________ Name and Signature _____________________ Date _____________________ Company Stamp ---------------------------------------------------------------------------- -- ****************************************************** 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)