No.1185

2000/10/30〜2000/11/02

岩間　一雄

Kazuo Iwama

目　次

1. Expected Length of Longest Common Subsequences of Two Biased Random Strings and Its Application (Algorithm Engineering as a New Paradigm)---1

　　　　群馬大学工学部/駒沢大学文学部/群馬大学工学部　　　青木 洋延/上原 隆平/山崎 浩一　(Aoki,Hironobu/Uehara,Ryuhei/Yamazaki,Koichi)

　

2. Distributed Motion Generation for Carrying a Ladder by Two Omni-Directional Robots (Algorithm Engineering as a New Paradigm)-----11

　　　　九州大学システム情報科学研究院///九州大学システム情報科学研究院//九州大学システム情報科学研究院　　　朝広 雄一///長藤 俊介/鈴木 一郎/山下 雅史　(Asahiro,Yuichi/Chang,Eric Chung-Hui/Mali,Amol/Nagafuji,Syunsuke/Suzuki,Ichiro/Yamashita,Masafumi)

　

3. Digital Halftoning : Formulation as a Combinatorial Optimization Problem and Approximation Algorithms Based on Network Flow (Algorithm Engineering as a New Paradigm)---18

　　　　北陸先端科学技術大学院大学情報科学研究科/北陸先端科学技術大学院大学情報科学研究科/京都大学工学研究科/東京大学工学系研究科/豊橋技術科学大学情報工学系/東北大学情報学研究科/(株)富士通　　　浅野 哲夫/藤川 直樹/加藤 直樹/松井 知己/永持 仁/徳山 豪/臼井 信昭　(Asano,Tetsuo/Fujikawa,Naoki/Katoh,Naoki/Matsui,Tomomi/Nagamochi,Hiroshi/Tokuyama,Takeshi/Usui,Nobuaki)

　

4. A Generic Tool for Interactive Visualization of Geometric Algorithms : GeoWin (Algorithm Engineering as a New Paradigm)----------28

　　　　Fachbereich IV - Informatik, Universitat Trier/Fachbereich IV - Informatik, Universitat Trier　　　Basken,Matthias/Naher,Stefan

　

5. Detecting Undersampling in Surface Reconstruction (Algorithm Engineering as a New Paradigm)--------------------------------------36

　　　　Department of CIS, Ohio State University/Department of CIS, Ohio State University　　　Dey,Tamal K./Giesen,Joachim

　

6. Cost optimal parallel algorithms for $P$-complete problems (Algorithm Engineering as a New Paradigm)-----------------------------53

　　　　九州工業大学情報工学部/奈良先端科学技術大学院大学情報科学研究科/奈良先端科学技術大学院大学情報科学研究科　　　藤原 暁宏/井上 美智子/増沢 利光　(Fujiwara,Akihiro/Inoue,Michiko/Masuzawa,Toshimitsu)

　

7. An algebraic approach to matching problems (Algorithm Engineering as a New Paradigm)---------------------------------------------63

　　　　Department of Combinatorics & Optimization, University of Waterloo　　　Geelen,James F.

　

8. Preemptive scheduling with rejection (Algorithm Engineering as a New Paradigm)---------------------------------------------------72

　　　　Department of Computer Science, Utrecht University/Fachbereich Mathematik, MA 6-1, Technische Universitat Berlin/Institut fur Mathematik, TU Graz　　　Hoogeveen,Han/Skutella,Martin/Woeginger,Gerhard J.

　

9. Some Complexity Issues in Parallel Computing (Algorithm Engineering as a New Paradigm)-------------------------------------------81

　　　　Department of Computer Science, University of California, Santa Barbara　　　Ibarra,Oscar H.

　

10. Towards an Optimal Oblivious Routing Algorithm on 2D Meshes (Algorithm Engineering as a New Paradigm)---------------------------90

　　　　京都大学情報学研究科/九州芸術工科大学芸術工学部　　　岩間 一雄/宮野 英次　(Iwama,Kazuo/Miyano,Eiji)

　

11. Integer Programming Based Algorithms for Peg Solitaire Problems (Algorithm Engineering as a New Paradigm)----------------------100

　　　　東京大学工学系研究科/東京大学工学系研究科　　　清見 礼/松井 知己　(Kiyomi,Masashi/Matsui,Tomomi)

　

12. Crystal Voronoi Diagram and Its Applications (Algorithm Engineering as a New Paradigm)-----------------------------------------109

　　　　東京大学工学系研究科/東京大学工学系研究科　　　小林 景/杉原 厚吉　(Kobayashi,Kei/Sugihara,Kokichi)

　

13. On Time Adaptivity and Stabilization (Algorithm Engineering as a New Paradigm)-------------------------------------------------120

　　　　Technion, Isarael　　　Kutten,Shay

　

14. Transformations on Regular Non-Dominated Coteries and Their Application (Algorithm Engineering as a New Paradigm)--------------130

　　　　大阪大学工学研究科　　　牧野 和久　(Makino,Kazuhisa/Kameda,Tiko)

　

15. グラフの構造的特徴と効率の良い並列アルゴリズムについて (新しいパラダイムとしてのアルゴリズム工学)------------------------------140

　　　　豊橋技術科学大学知識情報工学系/徳島大学総合科学部自然システム学科数理科学　　　増山 繁/中山 慎一　(Masuyama,Shigeru/Nakayama,Shin-ichi)

　

16. Quasi M-convex Functions and Minimization Algorithms (Algorithm Engineering as a New Paradigm)---------------------------------150

　　　　京都大学数理解析研究所/上智大学理工学部　　　室田 一雄/塩浦 昭義　(Murota,Kazuo/Shioura,Akiyoshi)

　

17. A Linear-Time Algorithm for Bend-Optimal Orthogonal Drawings of Biconnected Cubic Plane Graphs : Extended Abstract (Algorithm Engineering as a New Paradigm)---160

　　　　群馬大学工学部/群馬大学工学部　　　中野 眞一/吉川 万紀子　(Nakano,Shin-ichi/Yoshikawa,Makiko)

　

18. Metaheuristics : A General Framework (Algorithm Engineering as a New Paradigm)-------------------------------------------------169

　　　　School of Business and Center for Advanced Mathematical Sciences, American University of Beirut　　　Osman,Ibrahim H.

　

19. A hybrid GRASP with Perturbations for the Steiner Problem in Graphs (Algorithm Engineering as a New Paradigm)------------------171

　　　　Department of Computer Science, Catholic University of Rio de Janeiro/Department of Computer Science, Catholic University of Rio de Janeiro/Department of Computer Science, Catholic University of Rio de Janeiro　　　Ribeiro,Celso C./Uchoa,Eduardo/Werneck,Renato F.

　

20. Theory and practice of shift scheduling (Algorithm Engineering as a New Paradigm)----------------------------------------------172

　　　　Institut fur Informationssysteme, Technische Universitat Wien/Ximes Corp./Open University of Israel/Ximes Corp.　　　Slany,Wolfgang/Musliu,Nysret/Kortsarz,Guy/Gartner,Johannes

　

21. CKit : A Preprocessor for Algorithmic Experiments (Algorithm Engineering as a New Paradigm)------------------------------------182

　　　　Rutgers University　　　Szegedy,Mario

　

22. Recognition of Ordered Tree-Shellable Functions Based on OBDDs (Algorithm Engineering as a New Paradigm)-----------------------191

　　　　電気通信大学電気通信学部　　　武永 康彦　(Takenaga,Yasuhiko)

　

23. Efficient Augmentation to Construct $(\sigma + 1)$-Edge-Connected Simple Graphs (Algorithm Engineering as a New Paradigm)------199

　　　　広島大学工学研究科/広島大学工学研究科　　　田岡 智志/渡邉 敏正　(Taoka,Satoshi/Watanabe,Toshimasa)

　

24. On the design and analysis of evolutionary algorithms (Algorithm Engineering as a New Paradigm)--------------------------------209

　　　　FB Informatik, LS2, Univ. Dortmund　　　Wegener,Ingo

　

25. A Short Primer on the Primal-Dual Method for Approximation Algorithms (Algorithm Engineering as a New Paradigm)----------------221

　　　　IBM Almaden Research Center　　　Williamson,David P.