(r_<11>, r_<12>, r_<22>)-得点列対問題 : 構成可能性の判定

概要

論文の詳細を見る
大規模システムLSIの配線設計における配線経路の局所集中や通信ネットワークにおける回線の過剰負荷を避けるためにはネットワーク技術を用いた最適化技術が不可欠である。この最適化技術のための一手法として、有向完全グラフ構造をもつネットワークのフロー調節問題がある。この最適化問題はグラフ理論の得点列問題を用いることにより、さまざまな制約条件下での最適フローを実現できる。本稿では3つの正整数r_<11>, r_<12>, r_<22>, について、新しい得点列問題として(r_<11>, r_<12>, r_<22>)-得点列対問題と、S={S_1, S_2}が(r_<11>, r_<12>, r_<22>)-トーナメントの得点列かどうかをO(n)時間で判定する方法を提案する。ただし、S_1=(s_1[1], s_1[2], …, s_1[n_1]), S_2=(s_2[1], s_2[2], …, s_2[n_2])はそれぞれ非負整数列であり、n=n_1+n_2である。この問題を線形時間で判定することは、従来の得点列問題と同様の考察では困難であると考えられていた。今回、著者らは従来とは異なる手法を用いて、線形時間判定方法を見つけることができた。
社団法人電子情報通信学会の論文
2005-01-21