🚀 go-pugleaf

                  ----- Technical Program ----

                            ISAAC '92
        International Symposium on Algorithms & Computation
                  December 16-18, 1992, Nagoya, Japan

                   Organized by Nagoya University
  In Cooperation with IEICE TGCOMP, IPSJ SIGAL, ACM SIGACT and EATCS

The Third Annual International Symposium on Algorithms and Computation will
be held at Nagoya Congress Center, Nagoya, Japan, on December 16--18, 1992.
Its purpose is to provide a forum in Asia for researchers working in
algorithms and theory of computation.  The first symposium was held 1990 in
Tokyo, Japan, as SIGAL International Symposium on Algorithms, and the
second one was held 1991 in Taipei, Republic of China, as Second Annual
International Symposium on Algorithms.

I. PROGRAM

WEDNESDAY -- DECEMBER 16,1992

*Session 1: 9:30-11:30  (Invited Talks)

  Methods in Parallel Algorithmics
    U. Vishkin (U. Maryland, USA & Tel Aviv U., Israel)

  Rectilinear Paths among Rectilinear Obstacles
    D.T. Lee (Northwestern U., USA)

*Session 2A: 13:00-15:00

  Linear Time Algorithms for k-Cutwidth Problem
    M.H. Chen and S.L. Lee (National Chung Cheng U., ROC)
  
  The k-Edge-Connectivity Augmentation Problem of Weighted Graphs
    T. Mashima, S. Taoka, and T. Watanabe (Hiroshima U., Japan)

  Principal Lattice of Partitions of Submodular Functions on Graphs:
  Fast Algorithms for Principal Partition and Generic Rigidity
    S. Patkar and H. Narayanan (Indian Inst. of Tech., India)

  The Application of the Searching Over Separators Strategy
  to Solve Some NP-Complete Problems on Planar Graphs
    R.Z. Hwang (Chung Shan Inst. of Sci. and Tech., ROC) and
    R.C.T. Lee (National Tsing Hua U., ROC)

*Session 2B: 13:00-15:00

  Parallel and On-Line Graph Coloring Algorithms
    M. Halld'orsson (JAIST Hokuriku, Japan)

  Competitive Analysis of the Round Robin Algorithm
    T. Matsumoto (U. Tokyo, Japan)

  Competitive Analysis of the On-Line Algorithms for Multiple Stacks Systems
    B.C. Chien, R.J. Chen, and W.P. Yang (National Chiao Tung U., ROC)

  Self-Adjusting Augmented Search Trees
    T.W. Lai (U. Toronto, Canada)

*Session 3A: 15:30-17:30

  Algorithms for a Class of Min-Cut and Max-Cut Problems
    T.F. Gonzalez (U.C. Santa Barbara, USA) and T. Murayama (Sony Co., Japan)

  Algorithms for Rectilinear Optimal Multicast Tree Problem
    J.M. Ho, M.T. Ko, T.H. Ma, and T.Y. Sung (Academia Sinica, ROC)

  Approximating Treewidth and Pathwidth of Some Classes of Perfect Graphs
    T. Kloks and H. Bodlaender (Utrecht U., The Netherlands)

  Graph Spanners and Connectivity
    S. Ueno, M. Yamazaki (TITech, Japan), and
    Y. Kajitani (JAIST Hokuriku & TITech, Japan)

*Session 3B: 15:30-17:30

  Randomized Range-Maxima in Nearly-Constant Parallel Time
    O. Berkman (King's College London, UK),
    Y. Matias, and U. Vishkin (U. Maryland, USA & Tel Aviv U., Israel)

  Fault-Tolerant Broadcasting in Binary Jumping Networks
    Y. Han (U. Hong Kong, HK), Y. Igarashi (Gunma U., Japan),
    K. Kanai (Toshiba Co., Japan), and K. Miura (Gunma U., Japan)

  Routing Problems on the Mesh of Buses
    K. Iwama, E. Miyano (Kyushu U., Japan), and
    Y. Kambayashi (Kyoto U., Japan)

  Selection Networks with 8nlog_2n Size and O(log n) Depth
    S. Jimbo and A. Maruoka (Tohoku U., Japan)

THURSDAY -- DECEMBER 17, 1992

*Session 4: 9:30-11:30 (Invited Talks)

  Relativizations of the P $=$? NP and Other Problems:
  Some Developments in Structural Complexity Theory
    R. Book (U.C. Santa Barbara, USA)

  Boolean Circuit Complexity
    M. Paterson (U. Warwick, UK)

*Session 5A: 13:00-15:00

  Searching a Pseudo 3-Sided Solid Orthoconvex Grid
    A. Symvonis (U. Sydney, Australia) and
    S. Tragoudas (Southern Illinois U., USA)

  An Efficient Parallel Algorithm for Geometrically Characterizing
  Drawings of a Class of 3-D Objects
    N. D. Dendris, I. A. Kalafatis (U. Patras, Greece), and
    L. M. Kirousis (U. Patras & Computer Tech. Inst., Greece)

  Topologically Consistent Algorithms Related to Convex Polyhedra
    K. Sugihara (U. Tokyo, Japan)

  Characterizing and Recognizing Visibility Graphs of Funnel-Shaped Polygons
    S.H. Choi, S.Y. Shin and K.Y. Chwa (KAIST, Korea)

*Session 5B: 13:00-15:00

  On the Complexity of Composite Numbers
    T. Itoh and K. Horikawa (TITech, Japan)

  On Malign Input Distributions for Algorithms
    K. Kobayashi (TITech, Japan)

  Lowness and the Complexity of Sparse and Tally Descriptions
    V. Arvind (Indian Inst. of Tech., India),
    J. K"obler, and M. Mundhenk (U. Ulm, Germany) 

  Honest Iteration Schemes of Randomizing Algorithms
    J. Wang and J. Belanger (Wilkes U., USA)

*Session 6A: 15:30-17:30

  Sufficient Conditions for Triangulating 3-D Polyhedra with Applications
    B. Zhu (McGill U., Canada)

  Approximating Vertices of a Convex Polygon with Grid Points in the Polygon
    H.S. Lee (Tatung Inst. of Tech., ROC) and
    R.C. Chang (National Chiao Tung U., ROC)

  Algorithms for Determining the Geometrical Congruity
  in Two and Three Dimensions
    T. Akutsu (Mechanical Engineering Laboratory, Japan)

  On the Relationship among Constrained Geometric Structures
    E. Jennings and A. Lingas (U. Lund, Sweden)

*Session 6B: 15:30-17:30

  Generating Small Convergent Systems Can Be Extremely Hard
    K. Madlener, A. Sattler-Klein (U. Kaiserslautern, Germany), and
    F. Otto (Gesamthochschule Kassel, Germany)

  Chew's Theorem Revisited
  -- Uniquely Normalizing Property of Nonlinear Term Rewriting Systems --
    M. Ogawa (NTT, Japan)

  Higher Order Communicating Processes with Value-Passing, Assignment
  and Return of Results
    D. Bolignano and M. Debabi (Bull Co. Research Center, France)

  Searching Informed Game Trees
    W. Pijls and A. de Bruin (Erasmus U. Rotterdam, The Netherlands)

FRIDAY -- DECEMBER 18, 1992

*Session 7: 9:30-11:30 (Invited Talks)

  How to Generate Realistic Sample Problems for Network Optimization
    M. Iri (U. Tokyo, Japan)

  Generalized Assignment Problems
    S. Martello (U. Torino, Italy) and P. Toth (U. Bologna, Italy)

*Session 8A: 13:00-15:00

  Recognizing an Envelope of Lines in Linear Time
    E. Guevremont (McGill U., Canada) and
    J. Snoeyink (U. British Columbia, Canada)

  Approximation of Polygonal Curves with Minimum Number of Line Segments
    W. S. Chan and F. Chin (U. Hong Kong, HK)

  Wiring Knock-Knee Layouts -- A Global Approach
    M. Sarrafzadeh (Northwestern U., USA),
    F. Wagner (Freie U. Berlin, Germany),
    D. Wagner, and K. Weihe (Technische U. Berlin, Germany)

  An Algorithm for Finding Non-Crossing Paths
  with Minimum Total Length in Planar Graphs
    J. Takahashi, H. Suzuki and T. Nishizeki (Tohoku U., Japan)

*Session 8B: 13:00-15:00

  On Symmetry of Information and Polynomial Time Invertibility
    L. Longpre (Northeastern U., USA) and O. Watanabe (TITech, Japan)

  On Computational Power of Probabilistic ACC Circuits with Exact Output Gates
    R. Beigel (Yale U., USA), J. Tarui (U. Warwick, UK), and
    S. Toda (U. Electro-Comm., Japan)

  Computational and Statistical Indistinguishabilities
    K. Kurosawa and O. Watanabe (TITech, Japan)

  On Symmetric Differences of NP-Hard Sets with Weakly-P-Selective Sets
    B. Fu (Beijing Computer Inst. & U. Sci. and Tech. of China, China) and
    H. Z. Li (Yunnan Education College, China)

*Session 9A: 15:30-17:00

  Restricted Track Assignment with Applications
    M. Sarrafzadeh and D.T. Lee (Northwestern U., USA)

  A Simple Test for the Consecutive Ones Property
    W.L. Hsu (Academia Sinica, R.O.C)

  The Longest Common Subsequence Problem for Small Alphabet Size
  Between Many Strings
    K. Hakata and H. Imai (U. Tokyo, Japan)

*Session 9B: 15:30-17:00

  The Implicit Dictionary Problem Revisited
    T.W. Lam and K.H. Lee (U. Hong Kong, HK)

  Sorting In-Place with a Worst Case Complexity of nlog n-1.3n+O(log n)
  Comparisons and epsiron x nlog n+O(1) Transports
    K. Reinhardt (U. Stuttgart, Germany)

  Sorting and/by Merging Finger Trees
    A. Moffat (U. Melbourne, Australia), O. Petersson (Lund U., Sweden), and
    N.C. Wormald (U. Melbourne, Australia)

II. FOR FUTHER INFORMATION

The symposium guide including registration form is available via e-mail.
For recieving the guide, please send e-mail to issac@cs.titech.ac.jp