home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / theory / 1750 < prev    next >
Encoding:
Text File  |  1992-08-12  |  8.6 KB  |  254 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!sun-barr!sh.wide!wnoc-tyo-news!cs.titech!koudai!watanabe
  3. From: watanabe@cs.titech.ac.jp (Osamu Watanabe)
  4. Subject: ISAAC'92 Program
  5. Message-ID: <WATANABE.92Aug13155615@akagi.cs.titech.ac.jp>
  6. Sender: news@cs.titech.ac.jp (Usenet News System)
  7. Nntp-Posting-Host: akagi
  8. Organization: Tokyo Institute of Tech., Dept. of Computer Science, Japan
  9. Distribution: comp
  10. Date: Thu, 13 Aug 1992 06:56:15 GMT
  11. Lines: 241
  12.  
  13.                   ----- Technical Program ----
  14.  
  15.                             ISAAC '92
  16.         International Symposium on Algorithms & Computation
  17.                   December 16-18, 1992, Nagoya, Japan
  18.  
  19.                    Organized by Nagoya University
  20.   In Cooperation with IEICE TGCOMP, IPSJ SIGAL, ACM SIGACT and EATCS
  21.  
  22. The Third Annual International Symposium on Algorithms and Computation will
  23. be held at Nagoya Congress Center, Nagoya, Japan, on December 16--18, 1992.
  24. Its purpose is to provide a forum in Asia for researchers working in
  25. algorithms and theory of computation.  The first symposium was held 1990 in
  26. Tokyo, Japan, as SIGAL International Symposium on Algorithms, and the
  27. second one was held 1991 in Taipei, Republic of China, as Second Annual
  28. International Symposium on Algorithms.
  29.  
  30. I. PROGRAM
  31.  
  32. WEDNESDAY -- DECEMBER 16,1992
  33.  
  34. *Session 1: 9:30-11:30  (Invited Talks)
  35.  
  36.   Methods in Parallel Algorithmics
  37.     U. Vishkin (U. Maryland, USA & Tel Aviv U., Israel)
  38.  
  39.   Rectilinear Paths among Rectilinear Obstacles
  40.     D.T. Lee (Northwestern U., USA)
  41.  
  42. *Session 2A: 13:00-15:00
  43.  
  44.   Linear Time Algorithms for k-Cutwidth Problem
  45.     M.H. Chen and S.L. Lee (National Chung Cheng U., ROC)
  46.   
  47.   The k-Edge-Connectivity Augmentation Problem of Weighted Graphs
  48.     T. Mashima, S. Taoka, and T. Watanabe (Hiroshima U., Japan)
  49.  
  50.   Principal Lattice of Partitions of Submodular Functions on Graphs:
  51.   Fast Algorithms for Principal Partition and Generic Rigidity
  52.     S. Patkar and H. Narayanan (Indian Inst. of Tech., India)
  53.  
  54.   The Application of the Searching Over Separators Strategy
  55.   to Solve Some NP-Complete Problems on Planar Graphs
  56.     R.Z. Hwang (Chung Shan Inst. of Sci. and Tech., ROC) and
  57.     R.C.T. Lee (National Tsing Hua U., ROC)
  58.  
  59. *Session 2B: 13:00-15:00
  60.  
  61.   Parallel and On-Line Graph Coloring Algorithms
  62.     M. Halld'orsson (JAIST Hokuriku, Japan)
  63.  
  64.   Competitive Analysis of the Round Robin Algorithm
  65.     T. Matsumoto (U. Tokyo, Japan)
  66.  
  67.   Competitive Analysis of the On-Line Algorithms for Multiple Stacks Systems
  68.     B.C. Chien, R.J. Chen, and W.P. Yang (National Chiao Tung U., ROC)
  69.  
  70.   Self-Adjusting Augmented Search Trees
  71.     T.W. Lai (U. Toronto, Canada)
  72.  
  73. *Session 3A: 15:30-17:30
  74.  
  75.   Algorithms for a Class of Min-Cut and Max-Cut Problems
  76.     T.F. Gonzalez (U.C. Santa Barbara, USA) and T. Murayama (Sony Co., Japan)
  77.  
  78.   Algorithms for Rectilinear Optimal Multicast Tree Problem
  79.     J.M. Ho, M.T. Ko, T.H. Ma, and T.Y. Sung (Academia Sinica, ROC)
  80.  
  81.   Approximating Treewidth and Pathwidth of Some Classes of Perfect Graphs
  82.     T. Kloks and H. Bodlaender (Utrecht U., The Netherlands)
  83.  
  84.   Graph Spanners and Connectivity
  85.     S. Ueno, M. Yamazaki (TITech, Japan), and
  86.     Y. Kajitani (JAIST Hokuriku & TITech, Japan)
  87.  
  88. *Session 3B: 15:30-17:30
  89.  
  90.   Randomized Range-Maxima in Nearly-Constant Parallel Time
  91.     O. Berkman (King's College London, UK),
  92.     Y. Matias, and U. Vishkin (U. Maryland, USA & Tel Aviv U., Israel)
  93.  
  94.   Fault-Tolerant Broadcasting in Binary Jumping Networks
  95.     Y. Han (U. Hong Kong, HK), Y. Igarashi (Gunma U., Japan),
  96.     K. Kanai (Toshiba Co., Japan), and K. Miura (Gunma U., Japan)
  97.  
  98.   Routing Problems on the Mesh of Buses
  99.     K. Iwama, E. Miyano (Kyushu U., Japan), and
  100.     Y. Kambayashi (Kyoto U., Japan)
  101.  
  102.   Selection Networks with 8nlog_2n Size and O(log n) Depth
  103.     S. Jimbo and A. Maruoka (Tohoku U., Japan)
  104.  
  105. THURSDAY -- DECEMBER 17, 1992
  106.  
  107. *Session 4: 9:30-11:30 (Invited Talks)
  108.  
  109.   Relativizations of the P $=$? NP and Other Problems:
  110.   Some Developments in Structural Complexity Theory
  111.     R. Book (U.C. Santa Barbara, USA)
  112.  
  113.   Boolean Circuit Complexity
  114.     M. Paterson (U. Warwick, UK)
  115.  
  116. *Session 5A: 13:00-15:00
  117.  
  118.   Searching a Pseudo 3-Sided Solid Orthoconvex Grid
  119.     A. Symvonis (U. Sydney, Australia) and
  120.     S. Tragoudas (Southern Illinois U., USA)
  121.  
  122.   An Efficient Parallel Algorithm for Geometrically Characterizing
  123.   Drawings of a Class of 3-D Objects
  124.     N. D. Dendris, I. A. Kalafatis (U. Patras, Greece), and
  125.     L. M. Kirousis (U. Patras & Computer Tech. Inst., Greece)
  126.  
  127.   Topologically Consistent Algorithms Related to Convex Polyhedra
  128.     K. Sugihara (U. Tokyo, Japan)
  129.  
  130.   Characterizing and Recognizing Visibility Graphs of Funnel-Shaped Polygons
  131.     S.H. Choi, S.Y. Shin and K.Y. Chwa (KAIST, Korea)
  132.  
  133. *Session 5B: 13:00-15:00
  134.  
  135.   On the Complexity of Composite Numbers
  136.     T. Itoh and K. Horikawa (TITech, Japan)
  137.  
  138.   On Malign Input Distributions for Algorithms
  139.     K. Kobayashi (TITech, Japan)
  140.  
  141.   Lowness and the Complexity of Sparse and Tally Descriptions
  142.     V. Arvind (Indian Inst. of Tech., India),
  143.     J. K"obler, and M. Mundhenk (U. Ulm, Germany) 
  144.  
  145.   Honest Iteration Schemes of Randomizing Algorithms
  146.     J. Wang and J. Belanger (Wilkes U., USA)
  147.  
  148. *Session 6A: 15:30-17:30
  149.  
  150.   Sufficient Conditions for Triangulating 3-D Polyhedra with Applications
  151.     B. Zhu (McGill U., Canada)
  152.  
  153.   Approximating Vertices of a Convex Polygon with Grid Points in the Polygon
  154.     H.S. Lee (Tatung Inst. of Tech., ROC) and
  155.     R.C. Chang (National Chiao Tung U., ROC)
  156.  
  157.   Algorithms for Determining the Geometrical Congruity
  158.   in Two and Three Dimensions
  159.     T. Akutsu (Mechanical Engineering Laboratory, Japan)
  160.  
  161.   On the Relationship among Constrained Geometric Structures
  162.     E. Jennings and A. Lingas (U. Lund, Sweden)
  163.  
  164. *Session 6B: 15:30-17:30
  165.  
  166.   Generating Small Convergent Systems Can Be Extremely Hard
  167.     K. Madlener, A. Sattler-Klein (U. Kaiserslautern, Germany), and
  168.     F. Otto (Gesamthochschule Kassel, Germany)
  169.  
  170.   Chew's Theorem Revisited
  171.   -- Uniquely Normalizing Property of Nonlinear Term Rewriting Systems --
  172.     M. Ogawa (NTT, Japan)
  173.  
  174.   Higher Order Communicating Processes with Value-Passing, Assignment
  175.   and Return of Results
  176.     D. Bolignano and M. Debabi (Bull Co. Research Center, France)
  177.  
  178.   Searching Informed Game Trees
  179.     W. Pijls and A. de Bruin (Erasmus U. Rotterdam, The Netherlands)
  180.  
  181. FRIDAY -- DECEMBER 18, 1992
  182.  
  183. *Session 7: 9:30-11:30 (Invited Talks)
  184.  
  185.   How to Generate Realistic Sample Problems for Network Optimization
  186.     M. Iri (U. Tokyo, Japan)
  187.  
  188.   Generalized Assignment Problems
  189.     S. Martello (U. Torino, Italy) and P. Toth (U. Bologna, Italy)
  190.  
  191. *Session 8A: 13:00-15:00
  192.  
  193.   Recognizing an Envelope of Lines in Linear Time
  194.     E. Guevremont (McGill U., Canada) and
  195.     J. Snoeyink (U. British Columbia, Canada)
  196.  
  197.   Approximation of Polygonal Curves with Minimum Number of Line Segments
  198.     W. S. Chan and F. Chin (U. Hong Kong, HK)
  199.  
  200.   Wiring Knock-Knee Layouts -- A Global Approach
  201.     M. Sarrafzadeh (Northwestern U., USA),
  202.     F. Wagner (Freie U. Berlin, Germany),
  203.     D. Wagner, and K. Weihe (Technische U. Berlin, Germany)
  204.  
  205.   An Algorithm for Finding Non-Crossing Paths
  206.   with Minimum Total Length in Planar Graphs
  207.     J. Takahashi, H. Suzuki and T. Nishizeki (Tohoku U., Japan)
  208.  
  209. *Session 8B: 13:00-15:00
  210.  
  211.   On Symmetry of Information and Polynomial Time Invertibility
  212.     L. Longpre (Northeastern U., USA) and O. Watanabe (TITech, Japan)
  213.  
  214.   On Computational Power of Probabilistic ACC Circuits with Exact Output Gates
  215.     R. Beigel (Yale U., USA), J. Tarui (U. Warwick, UK), and
  216.     S. Toda (U. Electro-Comm., Japan)
  217.  
  218.   Computational and Statistical Indistinguishabilities
  219.     K. Kurosawa and O. Watanabe (TITech, Japan)
  220.  
  221.   On Symmetric Differences of NP-Hard Sets with Weakly-P-Selective Sets
  222.     B. Fu (Beijing Computer Inst. & U. Sci. and Tech. of China, China) and
  223.     H. Z. Li (Yunnan Education College, China)
  224.  
  225. *Session 9A: 15:30-17:00
  226.  
  227.   Restricted Track Assignment with Applications
  228.     M. Sarrafzadeh and D.T. Lee (Northwestern U., USA)
  229.  
  230.   A Simple Test for the Consecutive Ones Property
  231.     W.L. Hsu (Academia Sinica, R.O.C)
  232.  
  233.   The Longest Common Subsequence Problem for Small Alphabet Size
  234.   Between Many Strings
  235.     K. Hakata and H. Imai (U. Tokyo, Japan)
  236.  
  237. *Session 9B: 15:30-17:00
  238.  
  239.   The Implicit Dictionary Problem Revisited
  240.     T.W. Lam and K.H. Lee (U. Hong Kong, HK)
  241.  
  242.   Sorting In-Place with a Worst Case Complexity of nlog n-1.3n+O(log n)
  243.   Comparisons and epsiron x nlog n+O(1) Transports
  244.     K. Reinhardt (U. Stuttgart, Germany)
  245.  
  246.   Sorting and/by Merging Finger Trees
  247.     A. Moffat (U. Melbourne, Australia), O. Petersson (Lund U., Sweden), and
  248.     N.C. Wormald (U. Melbourne, Australia)
  249.  
  250. II. FOR FUTHER INFORMATION
  251.  
  252. The symposium guide including registration form is available via e-mail.
  253. For recieving the guide, please send e-mail to issac@cs.titech.ac.jp
  254.