[ISAAC98] Final Call for Participation

ISAAC '98 isaac98 at jupiter.kaist.ac.kr
Thu Dec 3 17:21:28 PST 1998


============================================================================
			FINAL CALL-FOR-PARTICIPATION
			----------------------------
                    Ninth Annual International Symposium
                        on Algorithms and Computation
============================================================================

                            December 14-16, 1998
                        Riviera Hotel, Taejon, Korea

                                Hosted by
         KAIST(Korea Advanced Institute of Science and Technology) 
                  KISS(Korea Information Science Society)

                              Sponsored by
                Ministry of Information and Communication
                Korea Science and Engineering Foundation
                 Information Processing Society of Japan
             Korea Information Society Development Institute


This symposium is intended to provide a forum for researchers working in
algorithms and theory of computation. It will be held in Taejon which is 
famous with hot spring resort, and is surrounded by historical landmarks 
of the ancient(18 B.C-A.D.660) civilization and beautiful mountains - 
Kyeryoung, Daedoon and Pomun.

Co-host KISS has been the professional
organization in Korea for those in computer and information sciences since
1973. The symposium is hosted in celebration of KISS's 25th anniversary.

Organization
------------
  o Program Committee Chair

   * Kyung-Yong Chwa (Co-Chair; KAIST, Korea)
   * Oscar Ibarra (Co-Chair; UC Santa Barbara, USA)

  o Program Committee

   * Takao Asano (Chuo U., Japan)
   * Ding-Zhu Du (U. of Minnesota, USA)
   * Susanne Hambrusch (Purdue U., USA)
   * Hiroshi Imai (U. of Tokyo, Japan)
   * Tao Jiang (McMaster U., Canada)
   * Sam Kim (Kyungpook Nat. U., Korea)
   * D.T. Lee (Northwestern U., USA)
   * Ming Li (U. of Waterloo, Canada)
   * Pandu Rangan (IIT, Madras, India)
   * Sartaj Sahni (U. of Florida, USA)
   * P. Spirakis (Comp. Tech. Inst., Patras, Greece)
   * Roberto Tamassia (Brown U., USA)
   * Shanghua Teng (U. of Illinois, USA)
   * Osamu Watanabe (Tokyo Inst. Tech., Japan)
   * Peter Widmayer (ETH, Zurich, Switzerland)
   * Chee K. Yap (Courant Inst. NYU, USA)
   * Hsu-Chun Yen (National Taiwan U., Taiwan)

  o Organizing Committee Chair

   * Jik Hyun Chang (Sogang U., Korea)

  o Organizing Committee
   * Hee-Chul Kim (Hankuk U. of Foreign Studies, Korea)
   * Sang-Ho Lee (Ewha Womans U., Korea)
   * Kunsoo Park (Seoul National U., Korea)

Invited Speaker
---------------
      o Bernard Chazelle(Princeton University and Ecole Polytechnique)
             "The Discrepancy Method"
      o Roberto Tamassia(Brown University)
             "Implementing Algorithms and Data Structures:
              An Educational and Research Perspective"

 Program
----------  
 Sunday, December 13, 1998
 6:00  Early Registration and Welcome Reception

 Monday, December 14, 1998
 8:30  Registration
 9:20  Opening Address

 Invited Presentation
 9:30  The Discrepancy Method - Abstract
       Bernard Chazelle (Princeton and Ecole Polytechnique)
 Coffee Break: 10:30 -- 11:00

 Session 1A: Geometry I
 11:00 $L_\infty$ Voronoi Diagrams and Applications to VLSI Layout and
       Manufacturing
       Evanthia Papadopoulou
 11:30 Facility Location on Terrains
       Boris Aronov, Marc van Kreveld, René van Oostrum, Kasturirangan
       Varadarajan
 12:00 Computing Weighted Rectilinear Median and Center Set in the Presence
       of Obstacles
       Joonsoo Choi, Chan-Su Shin, Sung Kwon Kim

 Session 1B: Complexity I
 11:00 Maximizing Agreement with a Classification by Bounded or Unbounded
       Number of Associated Words
       Hiroki Arimura, Shinichi Shimozono
 11:30 Disjunctions of Horn Theories and Their Cores
       Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino
 12:00 Checking Programs Discreetly: Demonstrating Result-Correctness
       Efficiently While Concealing It
       Giovanni Di Crescenzo, Kouichi Sakurai, Moti Yung
 Lunch: 12:30 --- 2:00

 Session 2A: Graph Drawing
 2:00  Two-Layer Planarization in Graph Drawing
       Petra Mutzel, René Weiskircher
 2:30  Computing Orthogonal Drawings in a Variable Embedding Setting
       Walter Didimo, Giuseppe Liotta
 3:00  Dynamic Grid Embedding with Few Bends and Changes
       Ulrik Brandes, Dorothea Wagner

 Session 2B: On-Line Algorithm and Scheduling
 2:00  Two New Families of List Update Algorithms
       Frank Schulz
 2:30  An Optimal Algorithm for On-Line Palletizing at Delivery Industry
       J. Rethmann, E. Wanke
 3:00  On-Line Scheduling of Parallel Jobs with Runtime Restrictions
       Stefan Bischof, Ernst W. Mayr
 Coffee Break: 3:30 -- 4:00

 Session 3A: CAD/CAM and Graphics
 4:00  Testing the Quality of Manufactured Disks and Cylinders
       Prosenjit Bose, Pat Morin
 4:30  Casting with Skewed Ejection Direction
       Hee-Kap Ahn, Siu-Wing Cheng, Otfried Cheong
 5:00  Repairing Flaws in a Picture Based on a Geometric Representation of
       a Digital Image
       Tetsuo Asano, Hiro Ito, Souichi Kimura, Shigeaki Shimazu

 Session 3B: Graph Algorithm I
 4:00  k-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary
       Multigraph
       Toshimasa Ishii, Hiroshi Nagamochi, Toshihide Ibaraki
 4:30  Polyhedral Structure of Submodular and Posi-modular Systems
       Hiroshi Nagamochi, Toshihide Ibaraki
 5:00  Maximizing the Number of Connections in Optical Tree Networks
       Thomas Erlebach, Klaus Jansen

 Tuesday, December 15, 1998

 Invited Presentation
 9:00  Implementing Algorithms and Data Structures: an Educational and
       Research Perspective - Abstract
       Roberto Tamassia (Brown)

 Session 4: Best Paper Presentation
 10:00 Selecting the k Largest Elements with Parity Tests
       Tak Wah Lam, Hing Fung Ting
 Coffee Break: 10:30 -- 11:00

 Session 5A: Randomized Algorithm
 11:00 Randomized K-Dimensional Binary Search Trees
       Amalia Duch, Vladimir Estivill-Castro, Conrado Martínez
 11:30 Randomized O(log log n)-Round Leader Election Protocols in Packet
       Radio Networks
       Koji Nakano, Stephan Olariu
 12:00 Random Regular Graphs with Edge Faults: Expansion through Cores
       Andreas Goerdt

 Session 5B: Complexity II
 11:00 A Quantum Polynomial Time Algorithm in Worst Case for Simon's
       Problem
       Takashi Mihara, Shao Chin Sung
 11:30 Generalized Graph Colorability and Compressibility of Boolean
       Formulae
       Richard Nock, Pascal Jappy, Jean Sallantin
 12:00 On the Complexity of Free Monoid Morphisms
       Klaus-Jörn Lange, Pierre McKenzie
 Lunch: 12:30 --- 2:00

 Session 6A: Graph Algorithm II
 2:00  Characterization of Efficiently Solvable Problems on
       Distance-Hereditary Graphs
       Sun-Yuan Hsieh, Chin-Wen Ho, Tsan-Sheng Hsu, Ming-Tat Ko, Gen-Huey
       Chen
 2:30  Fast Algorithms for Independent Domination and Efficient Domination
       in Trapezoid Graphs
       Yaw-Ling Lin
 3:00  Finding Planar Geometric Automorphisms in Planar Graphs
       Seok-Hee Hong, Peter Eades, Sang-Ho Lee

 Session 6B: Combinatorial Problem
 2:00  A New Approach for Speeding Up Enumeration Algorithms
       Takeaki Uno
 2:30  Hamiltonian Decomposition of Recursive Circulants
       Jung-Heum Park
 3:00  Convertibility among Grid Filling Curves
       Tetsuo Asano, Naoki Katoh, Hisao Tamaki, Takeshi Tokuyama
 Coffee Break: 3:30 -- 4:00

 Session 7A: Geometry II
 4:00  Generalized Self-Approaching Curves
       Oswin Aichholzer, Franz Aurenhammer, Christian Icking, Rolf Klein,
       Elmar Langetepe, Gunter Rote
 4:30  The Steiner Tree Problem in $\lambda_4$-geometry Plane
       Guo-Hui Lin, Guoliang Xue

 Session 7B: Computational Biology
 4:00  Approximation and Exact Algorithms for RNA Secondary Structure
       Prediction and Recognition of Stochastic Context-Free Languages
       Tatsuya Akutsu
 4:30  On the Multiple Gene Duplication Problem
       Michael Fellows, Michael Hallett, Ulrike Stege

 6:00     Conference Banquet

 Wednesday, December 16, 1998

 Session 8A: Geometry III
 9:00  Visibility Queries in Simple Polygons and Applications
       Boris Aronov, Leonidas J. Guibas, Marek Teichmann, Li Zhang
 9:30  Quadtree Decomposition, Steiner Triangulation, and Ray Shooting
       Siu-Wing Cheng, Kam-Hing Lee
 10:00 Optimality and Integer Programming Formulations of Triangulations in
       General Dimension
       Akira Tajima

 Session 8B: Approximation Algorithm
 9:00  Space-Efficient Approximation Algorithms for MAXCUT and COLORING
       Semidefinite Programs
       Philip N. Klein, Hsueh-I Lu
 9:30  A Capacitated Vehicle Routing Problem on a Tree
       Shin-ya Hamaguchi, Naoki Katoh
 10:00 Approximation Algorithms for Some Optimum Communication Spanning
       Tree Problems
       Bang Ye Wu, Kun-Mao Chao, Chuan Yi Tang
 Coffee Break: 10:30 -- 11:00

 Session 9A: Complexity III
 11:00 The Edge-Disjoint Paths Problem is NP-Complete for Partial k-Trees
       Xiao Zhou, Takao Nishizeki
 11:30 Inapproximability Results for Guarding Polygons without Holes
       Stephan Eidenbenz
 12:00 The Inapproximability of Non NP-hard Optimization Problems
       Liming Cai, David Juedes, Iyad Kanj

 Session 9B: Parallel and Distributed Algorithm
 11:00 An Efficient NC Algorithm for a Sparse $k$-Edge-Connectivity
       Certificate
       Hiroshi Nagamochi, Toru Hasunuma
 11:30 A Parallel Algorithm for Sampling Matchings from an Almost Uniform
       Distribution
       J. Diaz, J. Petit, P. Psycharis, M. Serna
 12:00 Optimal Approximate Agreement with Omission Faults
       Richard Plunkett, Alan Fekete


Proceedings
-----------
Accepted papers will be published in the proceedings of the
symposium(Lecture Notes in Computer Science, Volume 1533, Springer-Verlag).
Some selected papers will appear in Theoretical Computer Science as special issues.

Further Information
-------------------
If you have any question and request, do not hesitate to ask us. Fax number
is +82-42-869-3510 and e-mail address is isaac98 at jupiter.kaist.ac.kr.
The detailed information for transportation(including time tables for buses 
and trains), conference site map, and tourist attractions can be found 
at our web site: http://jupiter.kaist.ac.kr/~isaac98/

General Information
-------------------
  * Weather
Weather in December is mostly cold with occasional snows. Temperature ranges
between -5 degrees Centigrade and -2.5 degrees Centigrade(23F - 27.5F).

  * Currency Exchange
US $1 is about 1270 won. But nowadays, the exchange rate is fluctuating very
much. You can get the current exchange rate from internet.
(http://www.koexbank.co.kr/exchange_rating/newexchange2.html)
Credit cards, including VISA and Master Cards are accepted at hotels, 
department stores and restaurants.


Accommodation
-------------
Two hotels have been chosen as standard lodging for the conference.
One is Riviera hotel(the conference venue), and the other is Top hotel
(within easy walking distance to Riviera Hotel).
All rooms in Top hotel have been already reserved by pre-registers.
Thus you can get a room only in Riviera hotel, 
but the room is still served by special conference rates.
If you want rooms in hotels other than Riviera, we can check it instead of you.
	

Registration
------------
    Please, complete the form(with the  payment) and send it to the
    following address(FAX or postal mail only):

      Fax:    +82-2-360-2306
      Address:Ms. Cho, Tae-Nam
              Dept. of Computer Science and Engineering
              College of Engineering, Ewha Womans University
              11-1 Daehyun-dong, Seodaemun-ku, Seoul, Korea 120-750
      (E-Mail:isaac98 at mm.ewha.ac.kr)

------------------------------ cut here -----------------------------------

=======================================================================
             ISAAC'98 REGISTRATION/ACCOMMODATION FORM 
=======================================================================

                          Mail or fax to:
      Ms. Cho, Tae-Nam, Dept. of Computer Science and Engineering
           College of Engineering, Ewha Womans University,
        11-1 Daehyun-dong, Seodaemun-ku, Seoul, Korea 120-750
                       Fax: +82-2-360-2306


__ Male        __ Female
__ Dr.      __ Prof.     __ Researcher & Engineer    __ Student
__ Other (please specify)_________________

Family name:_________________ Given name:_________________

Affiliation:_________________________________________

Address:_____________________________________________

_____________________________________________________

_____________________________________________________

Phone:_________________  Fax:________________________

Email:_______________________________________________

Registration fee
================================================
   Regular          US $360 ___

   Student          US $240 ___
------------------------------------------------
Registration covers a copy of proceedings, reception on Dec. 13,
2 lunches, coffee and banquet on Dec. 15.  
The student fee does not include the banquet.

-----------------------------------------------------
Additional Tickets          Number        Amount
=====================================================
Banquet(US $50 each)        ______        ______
-----------------------------------------------------

-----------------------------------------------------------
Hotel Rates(Daily rates in US dollars per room (incl.tax).)
===========================================================
Category          Riviera (5 star)
===========================================================
Single(1)          95,000 won ___
Double(2)         105,000 won ___
Ondol(2)           95,000 won ___
-----------------------------------------------------------
(Ondol means a Korean traditional room which is heated by 
Korean under-floor heating system. There are no beds in 
the Ondol room. US $1 is about 1350 won. The exchange rate
is fluctuating very much.)

Arrival Date:_____________   Departure Date:_____________ 

I wish to share my room with:____________________________

(We will make a hotel reservation for you. To guarantee your 
reservation, a nonrefundable deposit(US $50) is required.  
The remaining hotel charge should be paid directly to the hotel.)


Grand Total
============
Registration fee + Room deposit + Banquet tickets 
                                    (optional)
= _______________


Payment
========
All payments should be made in US dollar through one of the
following means. Bank transfer is highly recommended.

* Bank transfer  
----------------
Name of the bank: Korea Exchange Bank Pangbaidong branch,
                  Seoul, Korea

Account number: 099-JSD-100740

Name of Account holder : KISS

Please enclose a copy of the bank transfer when sending the
registration form. 

* By credit card. Please complete
-----------------
  ___ VISA                   ___ MASTER

Card Number:_____________________________________________

Card Holder Name:________________________________________

Card Holder Address:_____________________________________

_________________________________________________________

Expires:_____________  Signature:________________________

Registration/reservation will be confirmed only after
payment has been received.

-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme



More information about the Compgeom-announce mailing list