平成１４年度第２回KSMAP

日時：７月１２日（金）　１５：００ 〜 １７：００ 

場所：京都大学工学部8号館3階 共同6号室

       会場への案内  

  「配置コストをもつ長方形詰込み問題に対する局所探索法の高速化」
    今堀 慎治 （京都大学大学院情報学研究科数理工学専攻） 講演要旨

  「Minimum Edge Ranking Spanning Tree Problem」
    宇野 裕之 （大阪府立大学総合科学部数理・情報科学科）講演要旨

長方形詰込み問題とは,様々な大きさの長方形を二次元平面上に互いに 重ならないように配置する問題であり,NP困難であることが知られている. これまでに,この問題に一般的な配置コストを導入し,局所探索法に基づく アルゴリズムを提案した.このアルゴリズムの特徴として,順列対表現を用いて 解を表現し,低次の多項式時間で順列対から配置を求めるという点が挙げられる.

本発表では,このアルゴリズムをもとに,局所探索において近傍内の解を順序よく 評価することによって,アルゴリズムの高速化を実現する手法を報告する.

An edge ranking of a graph is a labeling of edges with the property that every path between two edges with the same label $i$ contains an intermediate edge with label $j>i$. We introduce the problem of computing a minimum edge ranking spanning tree (MERST) of a given graph (i.e., find a spanning tree of a given graph whose edge ranking is minimum), which models parallel processing, and so on. The problem MERST turned out to be NP-hard for general graphs, and only a simple approximation algorithm has been proposed so far. However, we show that MERST has a polynomial time algorithm when a graph is threshold. The result is significant in the sense that it first finds a non-trivial graph class for which the problem MERST is polynomially solvable.