xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxx ISAAC '96 xxxxxxxxxxxxxx xxxxxxx xxxxxxxxxxxxxx xxxxxxx the 7th International Symposium on xxxxxxxxxxxxxx xxxxxxx Algorithms and Computation xxxxxxxxxxxxxx xxxxxxx December 16-18, 1996 xxxxxxxxxxxxxx xxxxxxx Senri Life Science Center xxxxxxxxxxxxxx xxxxxxx Osaka, Japan xxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx --------------------------------------------------------------------- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% SUNDAY, December 15, 1996 %%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% RECEPTION: 6:00 pm -- 8:00 pm Life Science Center, 9F %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% MONDAY, December 16, 1996 %%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Session 1: 9:30 -- 10:30 chair: Subhash Suri Applications of a Numbering Scheme for Polygonal Obstacles in the Plane by Mikhail Atallah (Purdue University) .........Break: 10:30 -- 10:45 am............ Session 2: 10:45 -- 11:45 chair: Satoru Miyano Multicast Communication in High Speed Networks. by Jonathan Turner (Washington University) .......Group Photo: 11:45 am -- noon......... .........Lunch: noon -- 13:30 pm............. Session 3a -- chair M. Atallah Computational Geometry (1) 13:30 Incremental convex hull algorithms are not output sensitive. ----- David Bremner 14:00 Separating and Shattering Long Line Segments. ----- Alon Efrat and Otfried Schwarzkopf 14:30 Optimal Line Bipartitions of Point Sets. ----- Olivier Devillers and Matthew J. Katz 15:00 Interval Finding and Its Application to Data Mining. ----- Takeshi Fukuda, Yasuhiko Morimoto, Shinichi Morishita and Takeshi Tokuyama Session 3b -- chair T. Akutsu Genome Science & Combinatorial Pattern Matching 13:30 On the Approximability of the Steiner Tree Problem in Phylogeny. ----- David Fern{\' a}ndez-Baca and Jens Lagergren 14:00 Approximation and Special Cases of Common Subtrees and Editing Distance. ----- Magn\'us M. Halld\'orsson and Keisuke Tanaka 14:30 Two-Dimensional Dynamic Dictionary Matching. ----- Ying Choi and Tak Wah Lam 15:00 Discovering Unbounded Unions of Pattern Languages from Positive Examples. ----- Alvis Br\=azma, Esko Ukkonen and Jaak Vilo .........Break: 15:30 -- 16:00 pm................ Session 4a -- chair M. Sharir Computational Geometry (2) 16:00 Extremal Problems for Geometric Hypergraphs. ----- Tamal K. Dey and J\'anos Pach 16:30 Computing Fair and Bottleneck Matchings in Geometric Graphs. ----- Alon Efrat and Matthew J. Katz 17:00 Computing the Maximum Overlap of Two Convex Polygons Under Translations. ----- Mark de Berg, Olivier Devillers, Marc van Kreveld, Otfried Schwarzkopf and Monique Teillaud Session 4b -- chair T. Hirata Graph Algorithms (1) 16:00 OBDDs of a Monotone Function and of Its Prime Implicants. ----- Kazuyoshi Hayase and Hiroshi Imai 16:30 Algorithms for Maximum Matching and Minimum Fill-in on Chordal Bipartite Graphs. ----- Maw-Shang Chang 17:00 Graph Searching on Chordal Graphs. ----- S. L. Peng, M. T. Ko, C. W. Ho, T. S. Hsu and C. Y. Tang %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% TUESDAY, December 17, 1996 %%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Session 5a -- chair M. Golin Graph Algorithms (2) 9:00 An Algorithm for Enumerating all Directed Spanning Trees in a Directed Graph. ----- Takeaki Uno 9:30 Vertex ranking of asteroidal triple-free graphs. ----- T. Kloks, H. M{\"u}ller and C. K. Wong Session 5b -- chair S. Miyano Complexity Theory (1) 9:00 Recursively Divisible Problems. ----- Rolf Niedermeier 9:30 StUSPACE($\log n$) in DSPACE($\log^2 n/\log\log n$). ----- Eric Allender and Klaus-J\"orn Lange .........Break: 10:00 -- 10:30 am............... Session 6a -- chair M. Golin Graph Algorithms (3) 10:30 Finding Edge-Disjoint Paths in Partial {\it k}-Trees. ----- Xiao Zhou, Syurei Tamura and Takao Nishizeki 11:00 Optimal Augmentation for Bipartite Componentwise Biconnectivity in Linear Time. ----- Tsan-sheng Hsu and Ming-Yang Kao 11:30 Towards More Precise Parallel Biconnectivity Approximation. ----- Ka Wong Chong and Tak Wah Lam Session 6b -- chair S. Miyano Complexity Theory (2) 10:30 The Complexity of Probabilistic versus Deterministic Finite Automata. ----- Andris Ambainis 11:00 Bounded Length Unambiguous Context-Free Grammar Equivalence. ----- B. Litow ........Lunch: noon -- 13:30 pm................... Session 7a -- chair D.-Z. Du Computational Geometry (3) 13:30 The Steiner Minimal Tree Problem in the ${\lambda}$-geometry Plane. ----- D.T. Lee and C.F. Shen 14:00 A Study of the {\it LMT}-skeleton. ----- Siu-Wing Cheng, Naoki Katoh and Manabu Sugai 14:30 A New Subgraph of Minimum Weight Triangulations. ----- Cao An Wang, Francis Chin and Yin-Feng Xu Session 7b -- chair Y. Igarashi Parallel & Distributed Algorithms (1) 13:30 Dynamic Tree Routing under the ``Matching with Consumption'' Model. ----- Grammati E. Pantziou, Alan Roberts and Antonis Symvonis 14:00 Dimension-Exchange Token Distribution on the Mesh and the Torus. ----- Michael E. Houle and Gavin Turner 14:30 Directed hamiltonian packing in d-dimensional meshes and its application. ----- Jae-Ha Lee, Chan-Su Shin and Kyung-Yong Chwa ..........Break: 15:30 -- 16:00 pm.................... Session 8a -- chair S. Suri Computational Geometry (4) 16:00 k-Pairs non-crossing shortest paths in a simple polygon. ----- Evanthia Papadopoulou 16:30 Minimum Convex Partition of a Polygon with Holes by Cuts in Given Directions. ----- A. Lingas and V. Soltan Session 8b -- chair J. Turner Parallel & Distributed Algorithms (1) 16:00 Efficient List Ranking on the Reconfigurable Mesh, with Applications. ----- Tatsuya Hayashi, Koji Nakano and Stephan Olariu 16:30 Periodic merging networks. ----- Miros{\l}aw Kuty{\l}owski, Krzysztof Lory\'s and Brigitte Oesterdiekhoff 17:00 Minimizing Wavelengths in an All-Optical Ring Network. ----- Gordon Wilfong %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% WEDNESDAY, December 18, 1996 %%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Session 9a -- chair V. Chandru Scheduling and On-line Algorithms (1) 9:00 Competitive Analysis of On-line Disk Scheduling. ----- Tzuoo-Hawn Yeh, Cheng-Ming Kuo, Chin-Laung Lei, and Hsu-Chun Yen 9:30 Scheduling interval ordered tasks with non-uniform deadlines. ----- Jacques Verriet Session 9b -- chair M. Ogihara Cryptography (1) 9:00 Cryptographic Weaknesses in the Round Transformation Used in a Block Cipher with Provable Immunity Against Linear Cryptanalysis. ----- Kouichi Sakurai and Yuliang Zheng 9:30 The multi-variable modular polynomial and its applications to cryptography. ----- Tsuyoshi Takagi and Shozo Naito .........Break: 10:00 -- 10:30 am...................... Session 10a -- chair V. Chandru Scheduling and On-line Algorithms (2) 10:30 Bounds and Algorithms for a Practical Task Allocation Model. ----- Tsan-sheng Hsu and Dian Rae Lopez 11:00 Scheduling Algorithms for Strict Multithreaded Computations. ----- Panagiota Fatourou and Paul Spirakis 11:30 On Multi-threaded Paging. ----- Esteban Feuerstein and Alejandro Strejilevich de Loma Session 10b -- chair M. Ogihara Cryptography (2) 10:30 A Fast and Efficient Homophonic Coding Algorithm. ----- Boris Ryabko and Andrey Fionov 11:00 An Improvement of the Digital Cash Protocol of Okamoto and Ohta. ----- Osamu Watanabe and Osamu Yamashita 12:00 End of program --------------------------------------------------------------------- REGISTRATION FORM for ISAAC '96 December 16-18, 1996, Osaka, Japan The registration fees for ISAAC '96 are listed below. To qualify for the early registration fee, your registration application must be postmarked by November 6th. The non-student registration fee includes the Sunday night reception, the Tuesday night banquet, the coffee breaks, and a copy of the proceedings. The student fee does not include the banquet. The registration fee does not include lunches. Since the symposium site is located in the middle of a large shopping center, you can easily find places for lunches. (Although on-site registration is possible, advance registration is highly recommended.) Please circle one category below. Category Fee After 11/06 member* 28,000 yen 32,000 yen Other 30,000 yen 34,000 yen Student 15,000 yen 20,000 yen *member of IPSJ, IEICE, ACM, IEEE, SIAM, or EATCS. Extra Banquet Tickets ......... x 12,000 yen each = .............. Total registration .................... The registration desk will be open Sunday, December 15 from 6 pm to 8 pm and during the conference meeting times. Payment and Remittance Please check the appropriate box. [ ] 1. Payment through Bank I have sent the Registration Fee on ...................... (Date) through ................................ to the follwoing (Bank name) account in Japanese yen. Bank Name: Sanwa Bank, Neyagawa Branch Account: ISAAC96 Account No.: 3926672 [ ] 2. Payment by Credit Card *overseas Participants Only [ ] Visa, [ ] Mastercard Card No.: ............................................... Name on Card: ........................................... Date of Expitation: ..................................... Amount of charge: ..................... yen I authorize Kindai Travel Inc., Osaka Japan to charge the amount as the registration fee for ISAAC '96. Signature: .............................................. Date: ..................... (Mon)/(Day)/(Year) Please send the completed form to the following address: Prof. Tetsuo Asano Attn: ISAAC '96 Dept. of Engineering Informatics, Osaka Electro-Comm. University 18-8 Hatsu-cho, Neyagawa, 572 JAPAN Fax: +81-720-24-0014 Cancellation and Refund: In case of the cancellation, written notification shoud be sent to Prof. Tetsuo Asano. Cancellation received on or before November 6th, 1996, 50\% cancel fee will be charged. No refunds for registartion can be made after November 6th, 1996. All refunds will be processed after the symposium. Note: Personal check and currency other than Japanese yen are not accepted, while money order is accepted. --------------------------------------------------------------------- Accomodation A block of rooms is reserved for the symposium at Senri Hankyu Hotel, which is only a five minutes walk from the symposium site. The rates for ISAAC '96 are posted and apply from Saturday, December 14 through Thursday, December 19, 1996. Hotel Reservation for Senri Hankyu Hotel Please check one: Single 9,630 yen ....... Twin 16,428 yen ....... The room charge includes tax and service charge. Arrival Date: .................. Departure Date: ................. Address .......................................................... .......................................................... .......................................................... Phone: ............................ Fax: ........................ E-mail: ....................................... Sharing room with ............................... Unfortunately hotel beds are not so long enough for tall people. If you are taller than 185cm, check here. [ ] In case of the cancellation, please send written notification or e-mail to Prof. Tetsuo Asano (asano@amlab.osakac.ac.jp). Send the completed form to Prof. Tetsuo Asano by a mail, Fax, or e-mail by November 6th, 1996. Prof. Tetsuo Asano Attn: ISAAC '96 Dept. of Engineering Informatics, Osaka Electro-Comm. University 18-8 Hatsu-cho, Neyagawa, 572 JAPAN Fax: +81-720-24-0014 e-mail: asano@amlab.osakac.ac.jp --------------------------------------------------------------------- General Information Location: The symposium and welcoming reception will take place at Senri Life Science Center in Osaka, Japan. Banquet will be held in Senri Hankyu Hotel nearby. Senri is located about 10km north of downtown Osaka, just 20 minutes-ride of Osaka subway. ACCOMODATION: A block of rooms is reserved for the symposium at Senri Hankyu Hotel, which is about 5-minutes walk from the symposium site. Reservation should be made by completing the Hotel Reservation Form and by sending it to Prof. Asano by a physical or electronic mail. The room block will be held until November 6th, 1996. Note that rooms will be assigned on a first-come first-served basis. Senri Hankyu Hotel Shin-Senri Higashimachi, Toyonaka, 565 JAPAN Phone: +81-6-872-2211 Fax: +81-6-832-2161 Room Charge (conference discount rate): Single Room: 9,630 yen Twin Room: 16,428 yen The rates above includ tax and service charge. Breakfast is not included. Other Hotels Nearby: Unfortunately there is no other hotel in the walking distance. However, there are many along Osaka Subway. Here is the list of those hotels. If you prefer the hotels below, you should make reservation for yourselves, by phone or by FAX. Most of the hotels below stand near subway stations. The distances from Senri-chuo station are : Esaka (3rd station), Shin-Osaka (5th station, 15 minutes), Umeda (8th station, 20 minutes), and Namba (12th station, 30 minutes). Hotel list: Osaka Sunpalace Single room 6500 yen or 7000 yen Twin room 13000 yen or 14000 yen or 15000 yen Double room 15000 yen Suite room 20000 yen or 25000 yen Japanese-style room 16200 yen or 22000 yen Phone +81-6-878-3804 FAX: +81-6-878-3456 5-minutes walk from Banpaku-Kouen Station of Osaka Mono-rail which is one station from Senri-Chuo. Very nice but somewhat inconvenient. Esaka Tokyu-inn Single room 9800 yen Twin room 16000 yen (including service charge, but excluding tax) Phone +81-6-338-0109 FAX: +81-6-338-8010 a few minutes walk from Esaka station Hotel Kleiton Esaka Single room 8,610 yen Twin room 14,162 yen (including service and tax) Phone +81-6-388-1211 FAX: +81-6-338-7011 a few minutes walk from Esaka station. Magii-in Esaka Single room 7000 yen Twin room 14000 yen Phone +81-6-821-2001 (excluding service and tax) a few minutes walk from Esaka station Hotel Parkside Single room 7000 yen or 7300 yen Twin room 10000 yen (including service and tax) Phone +81-6-386-9191 FAX: +81-6-386-9146 one minute walk from Esaka Station. Sunnystone Hotel Single room 5600 yen Twin room 8800 yen\ (including service and tax)\\ Phone +81-6-386-0001 FAX: +81-6-386-1631 one minute walk from Esaka Station. Second Sunnystone Hotel Single room 6400 yen Twin room 9800 yen (including service and tax)\\ Phone +81-6-386-3200 FAX: +81-6-386-3200 one minute walk from Esaka Station. Washington Hotel Single room 9,000 yen Twin room 17,000 yen Phone +81-6-303-8111 FAX: +81-6-302-7007 a few minutes walk from Shin-Osaka Station. Osaka Garden Palace Hotel Single room 6,800 yen Twin room 12,600 yen Phone +81-6-396-6211 FAX: +81-6-396-6220 15-minutes walk from Shin-Osaka Station. GETTING THERE: By air directly to Osaka: Osaka is one of the major cities in Japan. There are direct flights to Kansai International Airport from many countries. You can take trains from the airport. by air to Osaka After arriving in Kansai International Airport, take a train from the airport station: (1) Nankai RR: from airport to Namba station (1370 yen, 30 min.) and then take Osaka subway (Midosuji Line) from Namba to Senri-chuo terminal station (360 yen, 30 min.). Ordinary Express costs only 870yen although it takes more time. (It takes about five minutes to exchange trains from Nankai to Osaka Subway, but it is easy.) (2) JR West: from airport to Shin-Osaka station (2970 yen, 50 min.) ---rapid service is cheaper but slower--- and then take Osaka subway (Midosuji Line)} from Shin-Osaka to Senri-chuo terminal station (300 yen, 15 min.). It takes more than five minutes to exchange trains from JR train to Osaka Subway. There are many other routes between Kansai airport to Senri-chuo, but the above two routes are easiest and cheapest. by train to Osaka For those who arrive in Narita Tokyo Airport, take JR line from Narita to Tokyo, and then take Shinkansen (bullet train) from Tokyo to Shin-Osaka which takes about 3 hours and costs 13,480yen (one-way). Note: When buying a train ticket for subway, you should push a button KITAKYU before pushing a button indicating fares. The last three stations on the Midosuji Line belong to Kita-Osaka Kyuko (called KITAKYU). If you do not know how to buy a ticket, the best way is to buy a cheapest ticket and adjust it at Senri-chuo station. Symposium Site: The symposium will be held at: Senri Life Science Center Shin-Senri Higashimachi, Toyonaka, 565 JAPAN Phone: +81-6-873-2010 Fax: +81-6-873-2011 Senri Life Science Center is one-minute walk from Senri-chuo station of Osaka Subway (exactly speaking Kita-Osaka Kyukou). The north exit of the station is the closest. Osaka mono-rail station is at the opposite side. For Senri Hankyu Hotel you should take the south exit (near mono-rail station). Social Events: Reception There will be a welcome reception on Sunday December 15, 18:00-20:00, at the 9th floor of Senri Life Science Center. All the registrants are welcome. Banquet Symposium banquet will be in Senri Hankyu Hotel on Tuesday, December 17. Further Information: A detailed guide to Senri Life Science Center and Senri Hankyu Hotel will be sent with the receipt of your registration. Our Home Page of WWW includes detailed information. http://mediasv.media.osaka-cu.ac.jp/STAFF/isaac96/ Visa Citizens of some countries need to obtain a visa to enter Japan. Please consult travel agents as to whether you need it or not. If a document from the organizing Committee is needed for you to obtain a visa, please send e-mail to asano@amlab.osakac.ac.jp. JR Pass: The Japan Rail Pass offers visitors economy, flexibility and a simple-to-use advantage over regular fares. It entitles bearers unlimited travel on a vasr network of JR transportation without surcharge except for sleeping berths on trains and private compartments on Shinkansen and other limited expresses. (The Pass cannot be used for the new super express "Nozomi") An Exchange Order or voucher for the Pass must be purchased from authorized agents abroad prior to departure --- not after arrival in Japan. The Exchange Order Form is valid for 3 months after the issuing date, and can be exchanges for a Japan Rail Pass at the JR Travel Service Centers at major JR stations and Narita and Kansai airports. It costs 27,800 yen for 7-day pass, 44,200 yen for 14-day pass, and 56,600 yen for 21-day pass. Pass for children is also available. Green Pass is also available (although it is more expensive). The symposium is organized by Osaka Electro-Communication University, in cooperation with the Special Interest Group on Algorithms of the Information Processing Society of Japan anf the Technical Group on Theoretical Foundation of Computing of the Institute of Electronics, Information and Communication Engineers, the ACM Special Interest Group on Automata and Computability Theory, and European Association for Theoretical Computer Science. Organizing Committee Symposium Chairs: T. Asano (Osaka Electro-Communication. U., Japan), Y. Igarashi (Gunma U., Japan) Program Committee: T. Akutsu (Univ. of Tokyo, Japan), V. Chandru(Ind. Inst. Sci., India), D. Dobkin(Princeton U., USA), D.-Z. Du(U. of Minnesota, USA), H. ElGindy(U. of Newcastle, Australia), M. Golin(HK UST, Hong Kong), T. Hirata(Nagoya U., Japan), D. Kirkpatrick(UBC, Canada), A.K. Lenstra(Bellcore, USA), S. Miyano (U. of Tokyo, Japan, Co-Chair), M. Ogihara(Rochester, USA), W. Rytter(Warsaw, Poland), M. Sharir(Tel Aviv U., Israel and NYU, USA), S. Suri (Washington U., USA, Co-Chair), A. Srinivasan(Nat. U. Singapore, Singapore) Local Arrangement: N. Katoh (Kobe U. of Commerce, Japan), H. Nakano (Osaka City U., Japan) Publicity: D. Z. Chen (U. of Notre Dame, USA), T. Tokuyama (Tokyo Research Lab., IBM Japan) Finance: H. Suzuki (Ibaraki U., Japan) Publication: H. Nagamochi (Kyoto U., Japan) Advisory Committee F. Chin (Hong Kong Univ., Hong Kong) D-Z. Du (Chinese Academy of Sciences, China, and Univ. of Minnesota, USA) P. Eades (Univ. of Newcastle, Australia) W-L. Hsu (Academia Sinica, Taiwan) T. Ibaraki (Kyoto Univ., Japan) D.T. Lee (Northwestern Univ., USA) T. Nishizeki (Tohoku Univ., Japan, Chair)