Final Programme for ISAAC'97
======================
PROGRAMME for ISAAC-97
======================
16th DECEMBER 1997 (TUE)
-----------------------------------------------------------------------------
6:00pm Early Registration (Rosewood)
8:00pm Welcome Cocktail (Poolside)
-----------------------------------------------------------------------------
DAY 1: 17th DECEMBER 1997 (WED)
-----------------------------------------------------------------------------
8:15am REGISTRATION
-----------------------------------------------------------------------------
Symposium Opening (Ballroom B)
Session Chair: Chua Tat Seng
9:00am OPENING REMARKS by
Guest of Honour: Prof. Chong Chi Tat, DVC, NUS
9:30am KEYNOTE TALK : Prof. T. Ibaraki
Solving NP-hard combinatorial problems in the practical sense
-----------------------------------------------------------------------------
10:30am BREAK
-----------------------------------------------------------------------------
11:00am SESSION 1: (Ballroom B)
Transportation and Logistics (3 Papers)
Session Chair: Leong Hon Wai
Airline crew scheduling problem with many irregular flights
Akira Tajima and Shinji Misono
Practical approach to a facility location problem
for Large-Scale Logistics
Kazuyoshi Hidaka and Hiroyuki Okano
Hard instance generation for SAT
Satoshi Horie and Osamu Watanabe
-----------------------------------------------------------------------------
12:30pm LUNCH
-----------------------------------------------------------------------------
2:00pm SESSION 2A: (Ballroom B)
Combinatorial Alg. 1 (3 papers)
Session Chair: Lucas Hui
Playing tetris on meshes and multi-dimensional SHEARSORT
Miroslaw Kutylowski and Rolf Wanka
Formulation of the addition-shift-sequence problem and its complexity
Akihiro Matsuura and Akira Nagoya
Weighted and unweighted selection algorithms for k sorted sequences
Tatsuya Hayashi, Koji Nakano and Stephan Olariu
-----------------------------------------------------------------------------
2:00pm SESSION 2B: (Ballroom A)
Protocols (3 papers) **
(** Note: This session is Session 4B in the symposium proceedings.)
Session Chair: Lam Kwok Yan
A new efficient off-line anonymous cash scheme
Khanh Quoc Nguyen, Vijay Varadharajan and Yi Mu
On-line versus off-line in money-making strategies with brokerage
Eisuke Dannoura Kouichi Sakurai
Decision-making by hierarchies of discordant agents
XiaoTie Deng and Christos Papadimitriou
-----------------------------------------------------------------------------
3:30pm BREAK
-----------------------------------------------------------------------------
4:00pm SESSION 3A: (Ballroom B)
Graph Algorithms (2 papers)
Session Chair: Alan Gibbons
Algorithms for enumerating all perfect, maximum and
maximal matchings in bipartite graphs
Takeaki Uno
Augmenting edge and vertex connectivities simultaneously
Toshimasa Ishii, Hiroshi Nagamochi and Toshihide Ibaraki
-----------------------------------------------------------------------------
4:00pm SESSION 3B: (Ballroom A)
Logic: Horn Extension (2 papers)
Session Chair: T. Ibaraki
Two-face Horn extensions
Thomas Eiter, Toshihide Ibaraki and Kazuhisa Makino
Decremental maintenance of reachability in hypergraphs
and minimum models of Horn formulae
Giorgio Ausiello, Paolo Giulio Franciosa, Daniele Frigioni and
Roberto Giaccio
-----------------------------------------------------------------------------
5:00pm END OF TECHNICAL SESSIONS (DAY 1)
DAY 2: 18th DECEMBER 1997 (THU)
-----------------------------------------------------------------------------
Day 2 Opening (Ballroom B)
Session Chair: Hiroshi Imai
9:00am KEYNOTE TALK 2: Prof. C. E. Leiserson, MIT
Analysis of multithreaded algorithms
10:00am BEST PAPER PRESENTATION
A characterization of planar graphs by pseudo-line arrangements
Hisao Tamaki and Takeshi Tokuyama
-----------------------------------------------------------------------------
10:30am BREAK
-----------------------------------------------------------------------------
11:00am SESSION 4A: (Ballroom B)
Combinatorial Alg 2 (3 papers)
Session Chair: Tan Tiow Seng
Optimal fault-tolerant broadcasting in trees
Petrisor Panaite and Andrzej Pelc
A theoretical framework of hybrid approaches to MAX SAT
Takao Asano, Kuniaki Hori, Takao Ono and Tomio Hirata
Exponential lower bounds on the size of OBDDs representing
integer division
Takashi Horiyama and Shuzo Yajima
-----------------------------------------------------------------------------
11:00am SESSION 4B: (Ballroom A)
Network Routing Algorithms (3 papers) **
(** Note: This session is Session 2B in the symposium proceedings.)
Session Chair: Charles Leiserson
An adaptive distributed fault-tolerant routing algorithm
for the star graph
Leqiang Bai, H. Ebara, Hideo Nakano and Hajime Maeda
Multi-color routing in the undirected hypercube
Qian-Ping Gu and Hisao Tamaki
Competitive source routing on tori and meshes
Tzuoo-Hawn Yeh, Cheng-Ming Kuo, Chin-Luang Lei and Hsu-Chun Yen
-----------------------------------------------------------------------------
12:30pm LUNCH
-----------------------------------------------------------------------------
2:00pm SESSION 5A: (Ballroom B)
Parallel Graph Alg. (3 papers)
Session Chair: Pandu Rangan
Approximating unweighted connectivity problems in parallel
Zhi-Zhong Chen
A randomized linear work EREW PRAM algorithm to find
a minimum spanning forest
Chung Keung Poon and Vijaya Ramachandran
Efficient parallel algorithms for planar st-graphs
Mikhail J. Atallah, Danny Z. Chen and Ovidiu Daescu
-----------------------------------------------------------------------------
2:00pm SESSION 5B: (Ballroom A)
Computational Learning (3 papers)
Session Chair: Sanjay Jain
Peg-solitaire, string rewriting systems and finite automata
B. Ravikumar
On the size of probabilistic formulae
Hartmut Klauck
Homophonic coding with logarithmic memory size
Boris Ryabko and Andrey Fionov
-----------------------------------------------------------------------------
3:30pm BREAK
-----------------------------------------------------------------------------
4:00pm SESSION 6A: (Ballroom B)
Computational Geometry (2 papers)
Session Chair: D. T. Lee
Complexity and modeling aspects of mesh refinement into quadrilaterals
Rolf H. Mohring and Matthias Muller-Hannemann
Topology oriented vs exact arithmetic -- experience in implementing
the three-dimensional convex hull algorithm
Tsuyoshi Minakawa and Kokichi Sugihara
-----------------------------------------------------------------------------
4:00pm SESSION 6B: (Ballroom A)
Database Query Processing
Session Chair: Francis Chin
The complexity of learning branches and strategies from queries
Matthias Ott and Frank Stephan
Singularities make spatial join scheduling hard
Gabriele Neyer and Peter Widmayer
-----------------------------------------------------------------------------
5:00pm END OF TECHNICAL SESSIONS (DAY 2)
5:15pm Bus leave for banquet venue: Tang Dynasty Village
7:30pm CONFERENCE BANQUET
DAY 3: 19th DECEMBER 1997 (FRI)
-----------------------------------------------------------------------------
9:00am SESSION 7A: (Ballroom B)
VLSI Algorithms (3 papers)
Session Chair: Takao Nishizeki
A faster one-dimensional topological compaction algorithm
Hsiao-Feng Steven Chen and D. T. Lee
Algorithms for finding optimal disjoint paths around a rectangle
Wun-Tat Chan and Francis Y.L. Chin
An algorithm for finding a region with the minimum total
L_1 distance from prescibed terminals
Yoshiyuki Kusakari and Takao Nishizeki
-----------------------------------------------------------------------------
9:00am SESSION 7B: (Ballroom A)
Problems in Graph (3 papers)
Session Chair: K. Y. Chwa
On defect sets in bipartite graphs
P.E.Haxell and M.Loebl
Dynamic programming on distance-hereditary graphs
Maw-Shang Chang, Sun-Yuan Hsieh and Gen-Huey Chen
On the equivalence in complexity among basic problems on bipartite
and parity graphs
Serafino Cicerone and Gabriele Di Stefano
-----------------------------------------------------------------------------
10:30am BREAK
-----------------------------------------------------------------------------
11:00am SESSION 8A: (Ballroom B)
Computational Geometry 2 (3 papers)
Session Chair: Herbert Edelsbrunner
All-cavity maximum matchings
Ming-Yang Kao, Tak Wah Lam, Wing Kin Sung and Hing Fung Ting
Fast algorithms for computing \beta-skeletons and their relatives
S. V. Rao and Asish Mukhopadhyay
A branch-and-cut approach for minimum weight triangulation
Yoshiaki Kyoda, Keiko Imai, Fumihiko Takeuchi and Akira Tajima
-----------------------------------------------------------------------------
11:00am SESSION 8B: (Ballroom A)
Approximation Alg (3 papers)
Session Chair: Peter Eades
An efficient approximation scheme for the subset-sum problem
Hans Kellerer, Ulrich Pferschy and Maria Grazia Speranza
Competitive call control in mobile networks
Grammati E. Pantziou, George Pentaris and Paul Spirakis
Generalized swap-with-parent schemes for self-organizing sequential linear
lists
John Oommen and Juan Dong
-----------------------------------------------------------------------------
12:30pm LUNCH
-----------------------------------------------------------------------------
2:00pm Optional Tours to Research Institutions
-----------------------------------------------------------------------------
5:00pm END OF SYMPOSIUM
ISAAC'97 Home Page