asano@iscb.osakac.ac.JP (asano) (05/30/90)
================================================================= | SIGAL International Symposium on Algorithms | | | | August 16 - 18, 1990, Tokyo | | | | Organized by Special Interest Group on Algorithms (SIGAL) | | of the Information Processing Society of Japan (IPSJ) | ================================================================= Symposium Organization Symposium Chairs: Akihiro NOZAKI (International Christian University) Takao NISHIZEKI (Tohoku University) Program Committee: Toshihide IBARAKI (Kyoto University) (Chair) Tetsuo ASANO (Osaka Electro-Comm. University) (Co-Chair) Takao ASANO (Sophia University) Yoshihide IGARASHI (Gunma University) Hiroshi IMAI (Tokyo University) Kazuo IWANO (IBM Tokyo Research Laboratory) Tsutomu MATSUMOTO (Yokohama National University) Tetsuo MIZOGUCHI (Mitsubishi Electric Company, Ltd.) Katsuhiro NAKAMURA (NEC Co. Ltd.) Hideo NAKANO (Osaka University) Masafumi YAMASHITA (Hiroshima University) Hiroto YASUURA (Kyoto University) Finance: Katsuhiro NAKAMURA (NEC Co. Ltd.) Publication, Publicity: Hiroshi IMAI (Tokyo University) Local Arrangement Committee: Yoshihide IGARASHI (Gunma University) (Chair) Takao ASANO (Sophia University) (Co-Chair) Kazuo HIRONO (CSK Corporation) Kazuo IWANO (IBM Tokyo Research Laboratory) Mario NAKAMORI (Tokyo University of Agriculture and Technology) Takeshi TOKUYAMA (IBM Tokyo Research Laboratory) Shuji Tsukiyama (Chuo University) Shuichi UENO (Tokyo Institute of Technology) Osamu WATANABE (Tokyo Institute of Technology) GENARAL INFORMATION Location and Dates The Symposium will take place at the CSK Information Education Center 5-1, Suwa-2-chome, Tama, Tokyo 206 JAPAN on August 16 (Thursday) through 18 (Saturday), 1990 Language The official language during the symposium is English. Registration All participants, when they arrive at the symposium site, must go to the registration desk to notify us of your presence and to pick up the Symposium kit. The registration desk is open according to the following schedule: August 15, Wednesday 15:00-20:00 August 16, Thursday - 17, Friday 08:30-20:00 August 18, Saturday 08:30-12:00 Only preregistered participants can attend the Symposium. Those who are going to participate the Symposium have to fill in the registra- tion form below and return it with the payment on the registration fee to: Prof. Takao ASANO Department of Mechanical Engineering Sophia University Kioicho 7-1, Chiyoda-ku, Tokyo 102, Japan facsimile: +81-3-238-3885 Symposium fee No registration will be accepted unless it is accompanied by a correct payment of the following fee: with accomodation 40,000 yen (registered until July 5) with accomodation (with spouse) 70,000 yen (registered until July 5) without accomodation 20,000 yen (registered until July 5) without accomodation 25,000 yen (registered on and after July 6) 'The with accomodation' class includes board, and the 'without accomodation' class includes lunch. The registration fee includes participation in all scientific activities and social events. The registration fee also includes proceedings of the Symposium. Remittance Remittance should be made only by a bank transfer to the following account: Name of Account: SIGAL-ISA, representative Katsuhiro NAKAMURA Name of Bank: Mitsui Bank, Miyamaedaira Branch (No.244) Number of Account: 5232297 Personal checks, bank draft, traveller's checks, and credit cards are not acceptable. Hotel Accomodation CSK Information Education Center, where the Symposium is to be held, has 140 single rooms, all of which are to be used by the Symposium attendants. As there are few hotels near the Symposium site, it is recommended that registrants make reservation in the Center by choosing 'with accomodation' class in the registration form. Since the number of rooms is limited, rooms will be assigned on a first- come-first-served basis, and registrants are kindly requested to send the registration form at the earliest convenience. CSK Information Education Center has a swimming pool, a tennis court, an athletic gymnasium, and saunas, all free for the participant. The check in time is 15:00 (Wednesday), August 15, and the check out time is 10:00, August 19 (Sunday). Visas Citizens of some countries need to hold a visa to enter Japan. Please consult your travel agent or the Japanese Consulate as to whether you need one or not. If a document from the Organizing Committee is necessary for you to obtain a visa, please write to Prof. Takao NISHIZEKI SIGAL Symposium Chairman Department of Information Engineering, Faculty of Engineering, Tohoku University Sendai 980, Japan E-mail: nishi@jpntohok.bitnet facsimile: +81-22-263-9301 as soon as possible, because visa procedures are usually very slow. Climate and Clothing Generally speaking, the climate of Tokyo in Summer is hot and humid. The temperature in August is about 26+-4 degree in Celcius (or 78+-7 degree in Farenheit). Participants are advised to wear light clothing, such as half-sleeve shirts. However, we recommend that you carry a light sweater or a jacket, since the Symposium site and the main transportation systems in Japan are air-conditioned. SOCIAL EVENTS Welcoming Reception All participants and accompanying persons are invited to attend the Welcoming Reception which will start at 18:00, August 15 (Wednesday) at the SE Salon in the 7th floor of the Conference Building. Light meal (e.g. sandwitches) and drinks (wine, beer, or soft drinks) will be served. The registration fee covers this expense. Banquet A Banquet in Buffet STyle will be held at 18:00, August 16 (Thursday) at the Cafeteria in the Conference Building. All participants and accompanying persons are invited to attend the banquet. The registration fee covers this expense. TRANSPORTATION From Tokyo International Airport (Narita) to Shinjuku As there is no means of direct transportation from Tokyo International Airport at narita to the Symposium site, you have to move first to Shinjuku Station in Tokyo. Airport Limousine Buses run regularly between Airport and Shinjuku, leaving the airport every 20 minutes in the daytime. The bus stop you have to get off is 'Shinjuku Nishiguchi.' It takes about 120-150 minutes and costs 2,700 yen from the airport to Shinjuku. (It will cost about 25,000 yen by a taxi, so DO NOT catch a taxi at Narita airport.) If you are already in Tokyo or you have taken another bus, go to Shinjuku Station by JR (Japan Railway) train, subway, or a taxi. >From Shinjuku to the Symposium Site The direct transportation from Shinjuku to the Symposium site is Keio line. When you arrive in Shinjuku, you have to fing 'Keio Shinsen Shinjuku' (or 'Toei Shinjuku') station. Take a train for 'Tama Center' or 'Hashimoto' and get off at 'Nagayama' station, from which the Symposium site is within 5 minutes walk. Note that 'Keio Shinsen Shinjuku' station is different from 'Keio Shinjuku' station, and if you have taken a train from the latter, you have to get off at 'Chofu' station and take another train for Tama Center or Hashimoto. Also there are many other 'Shinjuku' stations for different lines, so you have to be careful not to take a train other than Keio line. Japan Railway Pass If you have a plan of visiting several cities in Japan, it is recommended to use the bullet train ('Shinkansen' in Japanese). The fare is 25,940 yen for a round trip between Tokyo and Kyoto. You can buy a special discount ticket in you country like EuRail Pass in Europe (note that you CANNOT buy one in Japan), which is called 'Japan Railway Pass.' The price depends on the period and is about 27,000 yen for one week and 43,000 yen for two weeks. With this pass you can take any train of Japan Railway freely. You can even reserve a seat in bullet trains. Please ask your travel agency for detail. Also, it is advised NOT TO travel for sightseeing in Japan before the Symposium, especially between the 10th and the 16th in August, since during this period traffics (trains, highways, airlines, and so on) are terribly crowded because of religious holidays. ================================================================= | SIGAL International Symposium on Algorithms | | | | August 16 - 18, 1990, Tokyo | | | | REGISTRATION FORM | ================================================================= Please: 1. Fill in one form per participant, 2. Type or print, 3. Keep a copy for your record, 4. Attach a copy of the order of bank transfer, and 5. Mail to Prof. takao ASANO (see below). Participant: _Mr. _ Ms. Family name ________________________________________ Given Name(s)________________________________________ Mailing Address: _Office _Home Affiliation____________________________________________________ ____________________________________________________ Address Street_____________________________________________ City_______________________________________________ Postal Code_____________ Country___________________ Phone___________________ Facsimile_______________ E-mail__________________ Accompanying person: if any _Mr. _Ms. ______________________________________ Registration Fee (including social events and proceedings): _with accomodation 40,000 yen (registered until July 5) _with accomodation (with spouse) 70,000 yen (registered until July 5) _without accomodation 20,000 yen (registered until July 5) _without accomodation 25,000 yen (registered on and after July 6) Arrival/Departure: Arrival Date_____________________ Time ____________________ Departure Date_____________________ Time ____________________ I remitted the above amount _______yen on ________________(date) through _____________________________________(name of bank) to the account of SIG-SA, representative Katsuhiro Nakamura, A/C No. 5232297 (ordinary deposit), Miyamaedaira Branch (No. 244), Mitsui Bank and am attaching hereto a copy of the order. Date:___________________ Signature:_________________________________ Note: All payments must be made in Japanese Yen. Personal checks, bank draft, traveller's checks, and credit cards are not acceptable. this application will become valid upon receipt of confirmation from the Conference Office. Since we can afford only a limited number of rooms for accomodation, please registrate at your earliest convenience. Mail this form form: ------------------------------------------ | Prof. Takao ASANO | | Department of Mechanical Engineering | | Sophia University | | Kioicho 7-1, Chiyoda-ku, Tokyo 102 | | Japan | ------------------------------------------ A brochure including several maps is available. For the brochure, please write to or send e-mail to Prof. Takao ASANO, Local Arrangement Co-chair of the symposium. --------------------------------------------- | E-MAIL: t_asano@hoffman.cc.sophia.ac.jp | --------------------------------------------- ================================================================= | SIGAL International Symposium on Algorithms | | | | August 16 - 18, 1990, Tokyo | | | | PROGRAM | ================================================================= Thursday, August 16 9:15 Opening of the Symposium Session I-1: Invited Talk 9:30 Recent Progress in String Algorithms Z. Galil (Columbia Univ. and Tel Aviv Univ.) 10:30 Break (10 minutes) Session I-2: Invited Talk 10:40 Selection Networks N. Pippenger (Univ. of British Columbia) 11:40 LUNCH (90 minutes) Session A-1 1:10 Computing Edge-Connectivity in Multiple and Capacitated Graphs, H. Nagamochi and T. Ibaraki (Kyoto Univ.) 1:40 Efficient Sequential and Parallel Algorithms for Planar Minimum Cost Flow, H. Imai (Univ. of Tokyo) and K. Iwano (IBM Res., Tokyo Research Lab.) Session B-1 1:10 Structural Analysis on the Complexity of Inverting Function, O. Watanabe (Tokyo Inst. of Technology) and S. Toda (Univ. of Electro-Communications) 1:40 Oracles versus Proof Techniques That Do Not Relativize*, E. Allender (Rutgers Univ.) 2:10 Break (20 minutes) Session A-2 2:30 20-Relative Neighborhood Graphs Are Hamiltonian*, M.S. Chang (National Chung Cheng Univ.), C.Y. Tang and R.C.T. Lee (National Tsing Hua Univ.) 3:00 The K-Gabriel Graphs and Their Applications, T.-H. Su (National Chia Tung Univ.), and R.-C. Chang (National Chia Tung Univ.) Session B-2 2:30 Parallel Algorithms for Generating Subsets and Set Partitions, B. Djoki\'{c} (Univ. of Miami), M. Miyakawa, S. Sekiguchi (Electrotechnical Lab.), I. Semba (Ibaraki Univ.) and I. Stojmenovi\'{c} (Univ. of Ottawa) 3:00 Parallel Algorithms for Linked List and Beyond*, Y. Han (Univ. of Kentucky) 3:30} Break (20 minutes) Session A-3 3:50 Local Tournaments and Recognition of Proper Circular Arc Graphs*, J. Bang-Jensen (Univ. of Copenhagen), P. Hell and J. Huang (Simon Fraser Univ.) 4:20 Fast Algorithms for the Dominating Set Problem on Permutation Graphs, K.-H. Tsai and W.-L. Hsu (Northwestern Univ. and Academia Sinica) Session B-3 3:50 Two Probabilistic Results on Merging, W. F. de la Vega (Univ. Paris-Sud), S. Kannan (Univ. of California, Berkeley) and M. Santha (Univ. Paris-Sud) 4:20 Randomized Broadcast in Networks, U. Feige , D. Peleg (Weizmann Inst. of Science), P. Raghavan (IBM T.J. Watson Res. Ctr.) and E. Upfal (IBM Almaden Res. Ctr.) 6:00 Banquet --------------------------------------------------------------------- Friday, August 17 Session I-3: Invited Talk 9:30 On the Construction of Abstract Voronoi Diagrams, II R. Klein (Univ.-GHS-Essen), K. Mehlhorn and S. Meiser (Univ. des Saarlandes) 10:30 Break (10 minutes) Session I-4: Invited Talk 10:40 Searching in Higher Dimension B. Chazelle (Princeton Univ.) 11:40 LUNCH (90 minutes) Session A-4 1:10 Finding UExtrema with Unary Predicates*, D. Kirkpatrick and F. Gao (Univ. of British Columbia) 1:40 Implicitly Searching Convolutions and Computing Depth of Collision*, D. Dobkin (Princeton Univ.), J. Hershberger (DEC SRC), D. Kirkpatrick (Univ. of British Columbia) and S. Suri (Bellcore) Session B-4 1:10 Characterization for a Family of Infinitely Many Irreducible Equally Spaced Polynomials, T. Itoh (Tokyo Inst. of Technology) \\[2mm] 1:40 Distributed Algorithms for Deciphering, M. Cosnard and J.-L. Philippe (Ecole Normale Sup\'{e}rieure de Lyon) 2:10 Break (20 minutes) Session A-5 2:30 An Efficient Algorithm for Optimal Loop Parallelization, K. Iwano and S. Yeh (IBM Res., Tokyo Research Lab.) 3:00 Another View on the SSS* Algorithm, W. Pijls and A. de Bruin (Erasmus Univ. Rotterdam) Session B-5 2:30 Algorithms from Complexity Theory: Polynomial-Time Operations for Complex Sets*, L. A. Hemachandra (Univ. of Rochester) 3:00 Complexity Cores and Hard Problem Instances*, U. Sch\"{o}ning (Univ. Ulm) 3:30 Break (20 minutes) Session A-6 3:50 Spatial Point Location and Its Applications, X.-H. Tan, T. Hirata and Y. Inagaki (Nagoya Univ.) 4:20 Sublinear Merging and Natural Merge Sort, S. Carlsson, C. Levcopoulos and O. Petersson (Lund Univ.) 4:50 Constructing Strongly Convex Approximate Hulls with Inaccurate Primitives, L. J. Guibas (MIT and Cambridge Research Lab.), D. Salesin (Stanford Univ.) and J. Stolfi (DEC SRC) Session B-6 3:50 Computing Puiseux-Series Solutions to Determinantal Equations via Combinatorial Relaxation, K. Murota (Univ. of Tokyo) 4:20 Complexity of Probabilistic Versus Deterministic Automata*, R. Freivalds (Latvian State Univ.) 4:50 A Tight Lower Bound on the Size of Planar Permutation Networks*, M. Klawe (Univ. of British Columbia) and T. Leighton (MIT) Saturday, August 18 Session I-5: Invited Talk 9:30 Simultaneous Solution of Families of Problems R. Hassin (Tel Aviv Univ.) 10:30 Break (10 minutes) Session A-7 10:40 Algorithms for Projecting Points to Give the Most Uniform Distribution with Applications to Hashing, Te. Asano (Osaka Electro-Communication Univ.) and T. Tokuyama (IBM Res., Tokyo Research Lab.) 11:10 Topological Sweeping in Three Dimensions, E.G. Anagnostou (Univ. of Toronto), L.J. Guibas (MIT and Cambridge Research Lab.) and V. Polimenis (Univ. of California, Berkeley) Session B-7 10:40 Finding Least-Weight Subsequence with Few Processors, K.-F. Chan and T.-W. Lam (Univ. of Hong Kong) 11:10 Derandomization by Exploiting Redundancy and Mutual Independence, Y. Han (Univ. of Kentucky) and Y. Igarashi (Gunma Univ.) 11:40 LUNCH (90 minutes) Session A-8 1:10 Planar Separators and the Euclidean Norm, H. Gazit (Duke University) and G. Miller (Carnegie Mellon Univ. and Univ. of Southern California) 1:40 On the Complexity of Isometric Embedding in the Hypercube, D. Avis (McGill Univ.) Session B-8 1:10 Distributed Function Evaluation in the Presence of Transmission Faults, N. Santoro (Carleton Univ. and Univ. di Bari), and P. Widmayer (Freiburg Univ.) 1:40 Optimal Linear Broadcast, S. Bitan and S. Zaks (Technion) 2:10 Break (20 minutes) Session A-9 2:30 Graph Augmentation Problems for a Specified Set of Vertices, T. Watanabe, Y. Higashi and A. Nakamura (Hiroshima Univ.) 3:00 A Heuristic for the k-Center Problem with Vertex Weight, Q. Wang and K.H. Cheng (Univ. of Houston) Session B-9 2:30 Parallel Convexity Algorithms for Digitized Images on a Linear Array of Processors, H. M. Alnuweiri (King Fahd Univ. of Petroleum and Minerals) and V.K. Prasan Kumar (Univ. of Southern California) 3:00 Parallel Algorithms for Labeling Image Components, W.-J. Hsu and X. Lin (Michigan State Univ.) 3:30 Break (20 minutes) Session A-10 3:50 A Hyperplane Incidence Problem with Applications to Counting Distances, H. Edelsbrunner (Univ. of Illinois) and M. Sharir (New York Univ. and Tel Aviv Univ.) 4:20 Splitting a Configuration in a Simplex, K. Numata (Univ. of Electro-Communications Univ.) and T. Tokuyama (IBM Res., Tokyo Research Labs) 4:50 Weaving Patterns of Lines and Line Segments in Space, J. Pach (New York Univ. and Hungary Academy of Sciences), R. Pollack (New York Univ.) and E. Welzl (Freie Univ. Berlin) Session B10 3:50 Efficient Parallel Algorithms for Path Problems in Planar Directed Graphs, A. Lingas (Lund Univ.) 4:20 Parallel Algorithms for Finding Steiner Forests in Planar Graphs, H. Suzuki, C. Yamanaka and T. Nishizeki (Tohoku Univ.) 4:50 Optimally Managing the History of an Evolving Forest, V. J. Tsotras (Columbia Univ.), B. Gopinath (Rutgers Univ.) and G. W. Hart (Columbia Univ.) *invited papers