平成11（1999）年度　一般研究２実施報告書

課題番号	11−共研−2020			専門分類		2
研究課題名	離散構造とアルゴリズム
フリガナ 代表者氏名	フジシゲ サトル 藤重 悟			ローマ字		Fujishige Satoru
所属機関	大阪大学
所属部局	大学院基礎工学研究科
職　　名	教授
所在地
TEL				FAX
E-mail
URL
配分経費	研究費	0千円	旅　費		0千円		研究参加者数	24　人

研究目的と成果（経過）の概要

本研究集会の講演内容は,近代科学社より本として近く出版の予定である。各講演者に
講演内容を執筆していただき講演順に第1章から第5章としている。
　第1章(浅野孝夫氏著)は,最近,世界的に研究が活発になされている解決困難な組合
せ最適化問題の近似アルゴリズムの設計技法と解析について,浅野氏らによる最新の成果
も交えて広範な話題を分かりやすく詳細に述べられている。今後の研究の展開に向けての
示唆に富む解説である。第2章は,一般化安定集合問題(双向グラフ上の安定集合問題)
に対する田村明久氏の最近の研究成果とその周辺の話題をまとめたものである。パーフェ
クト双向グラフの概念の導入とアルゴリズムを通して,組合せ多面体論の神髄に触れるこ
とができる。第3章(加藤直樹氏著)は,計算幾何学の基本問題であるk-セット問題と
それに双対なk-レベル問題に関する加藤氏らの最近の成果をまとめたもので,k-セット問
題と加藤氏が永年取り組んでいるパラメトリック最適化との見事な融合が見られて興味深
い。第4章(櫻井幸一氏著)では,インターネット社会を迎えてホットな話題となってい
るセキュリティに関わる公開鍵暗号の設計と安全性について,最新の成果がまとめられ,
解決すべきいくつかの課題が示されている。第5章は,著者の中野眞一氏が精力的に取り
組んでいる平面グラフの平面描画アルゴリズム(平面格子直線描画)について,詳細に述
べられている。平面描画の'おもしろさ'と'むつかしさ'を知ることができる。

当該研究に関する情報源（論文発表、学会発表、プレプリント、ホームページ等）

研究会を開催した場合は、テーマ・日時・場所・参加者数を記入してください。

研究参加者一覧
氏名	所属機関
浅野 哲夫	北陸先端科学技術大学院大学
茨木 俊秀	京都大学
今井 桂子	中央大学
今井 浩	東京大学
伊理 正夫	中央大学
岩田 覚	大阪大学
加藤 直樹	京都大学
久保 幹雄	東京商船大学
小島 政和	東京工業大学
櫻井 幸一	九州大学
杉原 厚吉	東京大学
田辺 國士	統計数理研究所
玉木 久夫	明治大学
田村 明久	電気通信大学
土谷 隆	統計数理研究所
中野 眞一	東北大学
永持 仁	京都大学
西関 隆夫	東北大学
福島 雅夫	京都大学
増山 繁	豊橋技術科学大学
松井 知巳	東京大学
水野 眞治	統計数理研究所
室田 一雄	京都大学