◆◇學術研討會◆◇ 第四屆國際計算與組合研討會(COCOON'98) 會議時間:87年8月12-14日 會議地點:資訊所科學研究一樓演講廳 主辦單位:資訊科學研究所 Program Information August 11, Tuesday ================== 06:00 PM--09:00 PM Registration 07:00 PM--09:00 PM Reception August 12, Wednesday ==================== 08:00 AM Registration 08:50 AM--09:00 AM Opening 09:00 AM--10:00 AM Invited talk I: Christos Papadimitriou Title: On Certain Algorithmic Approaches to Information Retrieval and Data Mining 10:30 AM--12:10 PM Section A: Computational Geometry Title: On Computing New Classes of Optimal Triangulations with Angular Constraints Author(s): Yang Dai and Naoki Katoh Title: Maximum Weight Triangulation and Its Application on Graph Drawing Author(s): Cao An Wang, Francis Y. Chin and Bo Ting Yang Title: The Colored Sector Search Tree: A Dynamic Data Structure for Efficient High Dimensional Nearest-Foreign-Neighbor Queries Author(s): T. Graf, V. Kamakoti, N.S. Janaki Latha and C. Pandu Rangan Title: Space-Efficient Algorithms for Approximating Polygonal Curves in Two Dimensional Space Author(s): Danny Z. Chen and Ovidiu Daescu Title: Parallel Geometric Algorithms in Coarse-Grain Network Models Author(s): Mikhail J. Atallah and Danny Z. Chen 01:00 PM--02:00 PM Invited talk II: Fan Chung Graham Title: Combinatorial Problems Arising in Massive Data Sets 02:30 PM--03:50 PM Section B: Algorithms and Data Structures (I) Title: On the Bahncard Problem Author(s): Rudolf Fleischer Title: The Ultimate Strategy to Search on m Rays? Author(s): Alejandro Lopez-Ortiz and Sven Schuierer Title: Better Approximation of Diagonal-Flip Transformation and Rotation Transformation Author(s): Ming Li and Louxin Zhang Title: A Cost Optimal Parallel Algorithm for Computing Force Field in N-Body Simulations Author(s): Guoliang Xue 04:10 PM--05:30 PM Section C: Algorithms and Data Structures (II) Title: Efficient 2 and 3-Flip Neighborhood Search Algorithms for the MAX SAT Author(s): Mutsunori Yagiura and Toshihide Ibaraki Title: Algorithms for Almost-uniform Generation with an Unbiased Binary Source Author(s): Omer Egecioglu and Marcus Peinado Title: Improved Algorithms for Chemical Threshold Testing Problems Author(s): Annalisa De Bonis, Luisa Gargano and Ugo Vaccaro Title: Min-Max-Boundary Domain Decomposition Author(s): Marcos Kiwi, Daniel A. Spielman and Shang-Hua Teng August 13, Thursday =================== 08:30 AM Registration 09:00 AM--10:00 AM Invited talk III: Michael Fischer Title: Estimating Statistics of Monotone Boolean Functions 10:30 AM--12:30 PM Section D: Computational Complexities Title: On Boolean Lowness and Boolean Highness Author(s): Steffen Reith and Klaus W. Wagner Title: The Inherent Dimension of Bounded Counting Classes Author(s): Ulrich Hertrampf Title: An Exact Characterization of Symmetric Functions in qAC°[2] Author(s): Chi-Jen Lu Title: Robust Reductions Author(s): Jin-Yi Cai, Lane A. Hemaspaandra and Gerd Wechsung Title: Approaches to Effective Semi-Continuity of Real Functions Author(s): Vasco Brattka, Klaus Weihrauch and Xizhong Zheng Title: On the Power of Additive Combinatorial Search Model Author(s): Vladimir Grebinski August 14, Friday ================= 08:30 AM Registration 09:00 AM--10:00 AM Invited talk IV: Rao Kosaraju Title: De-amortization of Algorithms 10:30 AM--12:10 PM Section E: Parallel and Distributed Processing and Switching Networks Title: The Number of Rearrangements in a 3-stage Clos Network Using an Auxiliary Switch Author(s): Frank K. Hwang and Wen-Dar Lin Title: Lower Bounds for Wide-Sense Non-Blocking Clos Network Author(s): Kuo-Hui Tsai and Da-Wei Wang Title: Multirate Multicast Switching Networks Author(s): Dongsoo S. Kim and Ding-Zhu Du Title: Efficient Randomized Routing Algorithms on the Two-Dimensional Mesh of Buses Author(s): Kazuo Iwama, Eiji Miyano, Satoshi Tajima and Hisao Tamaki Title: Executing Divisible Jobs on a Network with a Fixed Number of Processors Author(s): Tsan-sheng Hsu and Dian Rae Lopez 01:00 PM--02:20 PM Section F: Graph Theory (I) Title: On the Adam Conjecture on Circulant Graphs Author(s): Bernard Mans, Francesco Pappalardi and Igor Shparlinski Title: Proof of Toft's Conjecture: Every Graph Containing no Fully Odd K4 is 3- Colorable Author(s): Wenan Zang Title: A New Family of Optimal 1-Hamiltonian Graphs with Small Diameter Author(s): Jeng-Jung Wang, Ting-Yi Sung, Lih-Hsing Hsu and Men-Yang Lin Title: A Linear-Time Algorithm for Constructing an Optimal Node-Search Strategy of a Tree Author(s): Sheng-Lung Peng, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko and Chuan Yi Tang 02:40 PM--03:40 PM Section G: Graph Theory (II) Title: A Graph Optimization Problem in Virtual Colonoscopy Author(s): Jie Wang and Yaorong Ge Title: Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance Matrices Author(s): Bang Ye Wu, Kun-Mao Chao and Chuan Yi Tang Title: An Optimal Algorithm for Finding the Minimum Cardinality Dominating Set on Permutation Graphs Author(s): H. S. Chao, F. R. Hsu and R. C. T. Lee 04:00 PM--05:40 PM Section H: Combinatorics and Cryptography Title: Similarity in Two-Dimensional Strings Author(s): Ricardo A. Baeza-Yates Title: On Multi-Dimensional Hilbert Indexings Author(s): Jochen Alber and Rolf Niedermeier Title: Combinatorial Properties of Classes of Functions Hard to Compute in Constant Depth Author(s): Anna Bernasconi Title: Eulerian Secret Key Exchange Author(s): Takaaki Mizuki, Hiroki Shizuya and Takao Nishizeki Title: One-Time Tables for Two-Party Computation Author(s): Donald Beaver 詳情請參閱網址:http://www.iis.sinica.edu.tw/cocoon98