2500件目記念インタビュー

Barrelの収録文献が平成21年7月21日に2500件を超えました!

2500件目の文献は,社会情報学科の石井利昌先生による,
Ishii, Toshimasa (2009) Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs, Discrete Optimization 6(1), pp23-36 でした。

石井先生にお話を伺いました。

MrNakatsugawaQ:登録2500件目の論文「Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs」は、どのような内容ですか?

私の研究対象は、離散最適化問題 (または組合せ最適化問題) です。本論文は、その一つである「グラフの連結度増加問題」を扱っています。ネットワーク上において、どの2点間も行き来できるとき、ネットワークは連結であるというのですが、どの k-1 本のリンク (k-1 個のノード)が故障しても連結性が壊れないとき, ネットワークの辺連結度 (点連結度) は k 以上であるといいます。この定義から、連結度はネットワークの耐故障性を表す尺度の一つと言えます。連結度増加問題とは、最小本数のリンク追加で目標の連結度を実現する問題です。つまり、できるだけ少ないコストで信頼性の高いネットワークを構築することを目的とする問題です。本論文では、辺連結度増加問題を拡張した「単調な要求をもつ」辺連結度増加問題に対して最適解を求める効率的なアルゴリズムを提案しています。


Q:この研究をはじめられたきっかけは何ですか?

グラフの連結度増加問題は、学生の頃から取り組んでいるテーマです。この問題の構造がどのように特徴づけられるかに興味があり、問題を一般化して考えたりしているのですが、本論文はその一つと位置づけられます。また、連結度増加問題の応用例は上記の耐故障性を有するネットワーク設計以外にあまり知られていないのですが、問題を一般化することにより他の離散最適化問題へ応用できないかなども考えています。


Q:現在の研究について教えてください。

連結度に関する問題のほかでは、最近興味を持って研究している問題に、彩色問題の一種である「L(2,1)-ラベリング問題」というものがあります。彩色問題に関しては、どんな地図でも隣の区画同士を異なる色で塗るには4色あればよいという四色定理がよく知られていますが、ご存知でしょうか? L(2,1)-ラベリング問題は、さらに条件が増えて、色を1, 2, 3,…と番号付けし、隣同士は番号が2以上離れていないといけない、1つおいた向こう側とは1以上離れていないといけない、という条件で塗り分けます。この問題は無線通信ネットワークにおける周波数割当などに応用があります。


Q:Barrelに掲載された文献をどのような人に読んでもらいたいですか。

いろいろな分野の人に読んでもらいたいですね。そして、連結度の概念や本論文の手法が使えそうな分野があれば是非教えていただきたいです。応用範囲が増えていけば、この研究分野の重要性もさらに高まるのではないかと思います。


Q:Barrelについてご意見,感想をお願いします。

すばらしいと思います。他の大学ももっと多くの論文を公開していっていただきたいです。本学は電子ジャーナルがあまり揃っていませんので、著者の最終バージョンでもすぐに入手できるのであれば本当に助かります。また、著者がウェブにファイルをアップしている場合もありますが、それより、Barrelや同種のサイトではそのファイルが最終バージョンだと分かり安心だという利点もあると思います。


recom. books  興味を持った方へ!...石井先生からのオススメ入門書

(1) 茨木俊秀:情報学のための離散数学,昭晃堂,2004.

(2) 浅野哲夫:アルゴリズム・サイエンス:入口からの超入門,共立出版,2006 

(3) 岩間一雄:アルゴリズム・サイエンス:出口からの超入門,共立出版,2006 

(4) 松井泰子,根本俊男,宇野毅明:入門オペレーションズ・リサーチ,東海大学出版会,2008

中でも,(4) は特に初心者向けだと思います.
また,飯田先生が紹介されている本もこの分野に対するいい入門書です.


青字は本学図書館で所蔵しています。リンクをクリックしてご確認ください。※この推薦本は、2009年12月7日に追記しました。

---
石井先生、お忙しい中、興味深いお話ありがとうございました!


研究者のみなさまのご協力のおかげで正式公開から1年5ヶ月足らずで登録文献数が2500編を越えました。ありがとうございました。2500編は先生方のご著作のほんの一部でしかありませんので、これからも先生方の研究成果の公開につとめていきたいと思っております。今後とも、ご著作をより多くの人々へ届けるため、論文等をBarrelへ寄贈いただきたくよろしくお願いいたします!