ナノ回路設計のためのグラフの理論とアルゴリズムに関する研究
【研究分野】情報学基礎
【研究キーワード】
アルゴリズム / グラフ / ナノ回路
【研究成果の概要】
直交半直線交差グラフ(平面上の水平あるいは垂直な半直線の集合を点集合とする交差グラフ)という新しいグラフのクラスを提案して,その離散構造を解明しました.この直交半直線交差グラフの理論に基づいて,次世代集積回路の革新的な技術として注目を集めているナノ回路の耐故障設計において重要な役割を果たす「直交半直線交差グラフの部分グラフ同型問題」とその特別な場合である「直交半直線交差グラフの均衡完全2部部分グラフ問題」に対して,前者はNP困難と呼ばれる難しい問題であるが,後者は多項式時間のアルゴリズムで効率的に解ける易しい問題であることを明らかにしました.
【研究代表者】
【研究種目】基盤研究(C)
【研究期間】2008 - 2010
【配分額】4,550千円 (直接経費: 3,500千円、間接経費: 1,050千円)