新しいパラダイムとしてのアルゴリズム工学

京都大学数理解析研究所の共同研究事業の一つとして、下記のように研究集会を
催しますので、ご案内申し上げます。

				研究代表者     岩 間    一 雄
					    （京都大学情報学研究科）
                 日 時：２０００年１０月３０日１３：００〜
                                  １１月  ２日１６：３０
                 場 所：京都大学数理解析研究所
                        京都市左京区北白川追分町
                        市バス 農学部前 または 北白川 下車



                 プログラム

October 30
13:00-15:00 	Invited talks
		- Stefan Naeher (title, abstract)
		- Tamal Krishna Dey (title, abstract)
		Break
15:30-17:30	Invited talks
		- Mario Szegedy (title, abstract)
		- Wolfgang Slany (title, abstract)

October 31
9:30-11:30	Invited talks
		- Ingo Wegener (title, abstract)
		- Oscar H. Ibarra (title, abstract)
		Lunch
13:00-15:00 	Group A02
		Night tour

November 1
9:30-11:30	Invited talks
		- James F. Geelen (title, abstract)
		- David Williamson (title, abstract)
		Lunch
13:00-15:00	Invited talks
		- Celso Ribeiro (title, abstract)
		- Ibrahim Osman (title, abstract)
		break
15:30-17:00	Group A01
		Banquet

November 2
9:30-11:30	Invited talks
		- Shay Kutten (title, abstract)
		- Gerhard Woeginger (title, abstract)
		Lunch
13:00-14:30	Group A03
		break
15:00-16:30	Group A04


A01 -------------------------------------------------------------------

Some structural features of graphs which make efficient parallel
algorithms possible
Shigeru Masuyama* (Toyohashi University of Technology), 
Shin-ichi Nakayama (University of Tokushima)

Transformations on Regular Non-Dominated Coteries
and Their Application
Kazuhisa Makino* (Osaka University),
Tiko Kameda (Simon Fraser University)
           
Quasi M-convex Functions and Minimization Algorithms
Kazuo Murota (Kyoto University), Akiyoshi Shioura* (Sophia University)



A02 -------------------------------------------------------------------

Expected Length of Longest Common Subsequences of Two Biased Random
Strings and Its Application
Hironobu Aoki, Ryuhei Uehara* (Komazawa University),
Koichi Yamazaki (Gunma University)

Recognition of Ordered Tree-Shellable Functions Based on OBDDs
Yasuhiko Takenaga (University of Electro-Communications)

Efficient Augmentation to Construct (σ+1)-Edge-Connected Simple Graphs
Satoshi Taoka, Toshimasa Watanabe (Hiroshima University)

Integer Programming Based Algorithm for Peg Solitaire Problems
Masashi Kiyomi*, Tomomi Matsui (The University of Tokyo)



A03----------------------------------------------------------------

Crystal Voronoi Diagram and Its Applications
Kei Kobayashi, Kokichi Sugihara (The University of Tokyo)

A Linear-Time Algorithm for Bend-Optimal Orthogonal Drawings 
of Biconnected Cubic Plane Graphs
Shin-ichi Nakano*, Makiko Yoshikawa (Gunma University)

Digital Halftoning: Formulation as a Combinatorial Optimization 
Problem and Approximation Algorithms Based on Network Flow
Tetsuo Asano (JAIST), Naoki Fujikawa (JAIST), 
Naoki Katoh (Kyoto University), Tomomi Matsui (University of Tokyo),
Hiroshi Nagamochi (Toyohasi University of Technology),
Takeshi Tokuyama (Tohoku University), 
and Nobuaki Usui (Fujitsu Laboratories Ltd.)



A04-------------------------------------------------------------------
Cost optimal parallel algorithms for P-complete problems
Akihiro Fujiwara* (Kyushu Institute of Technology),
Michiko Inoue, Toshimitsu Masuzawa (NAIST)
 
Distributed Motion Generation for Carrying a Ladder by Two
Omni-Directional Robots 
Yuichi Asahiro*, Eric Chung-Hui Chang, Amol Mali,
Syunsuke Nagafuji, Ichiro Suzuki, Masafumi Yamashita
(Kyushu University)

Towards an optimal oblivious routing algorithm on 2D meshes
Kazuo Iwama (Kyoto University), Eiji Miyano* (Kyushu Institute of Design)

-------------------------------------------------------------------------
invited talks


- Stefan Naeher (Universitaet Trier)
  A Generic Tool for Interactive Visualization of Geometric Algorithms (GeoWin)


- Tamal Krishna Dey (The Ohio State University)
  Detecting Undersampling in Surface Reconstruction


- Mario Szegedy (Princeton Institute for Advanced Studies)
  CKit: A Preprocessor for Algorithmic Experiments


- Wolfgang Slany (Technische Universitaet Wien)
  Theory and Practice of Shift Scheduling


- Ingo Wegener (University of Dortmund)
  On the Design and Analysis of Evolutionary Algorithms


- Oscar H. Ibarra (University of California)
  Some Complexity Issues in Parallel Computing


- James Ferdinand Geelen (University of Waterloo)
  An Algebraic Approach to Matching Problems


- David Williamson (IBM T. J. Watson Research Center)
  A Short Primer on the Primal-Dual Method for Approximation Algorithms


- Celso Ribeiro (Catholic University of Rio de Janeiro)
 A Hybrid GRASP with Perturbations and Adaptive Path-Relinking for the Steiner Problem in Graphs


- Ibrahim Osman (American University of Beirut)
  Metaheuristics: A General Framework


- Shay Kutten (Faculty of Industrial Engineering and Management,
                       Technion, Israel)
  On Time Adaptivity and Stabilization


- Gerhard Woeginger (Technical University Graz)
  Preemptive Scheduling with Rejection