耐故障ナノ回路設計に向けての直交半直線交差グラフに関する研究

１．直交半直線交差木の特徴付け：直交半直線交差グラフは耐故障ナノ回路設計に関連して定義されたグラフの族であり，効率的なナノ回路設計のためにこのグラフの構造に関する研究が必要とされている．グラフの構造に関する研究で重要なのがグラフの特徴付けと認識問題の計算量である．直交半直線交差木とは，閉路を含まない直交半直線交差グラフであり，いわば最も単純な場合の直交半直線交差グラフである．今年度，この直交半直線交差木の特徴付けを示すと共に，その認識問題が線形時間で解けることを明らかにた．この成果をまとめ，論文誌に発表した．２．台形グラフの同型問題のＧＩ完全性：グラフ同型問題とは，入力として与えられた２つのグラフが同じかどうかを判定する問題である．台形グラフとは２本の水平線の間に張られた台形の集合によって定義される交差グラフであり，台形グラフの補グラフの族は２方向直交半直線交差グラフの族を真に含む．台形グラフの同型問題の計算量は１０年以上未解決問題であったが，今年度それがＧＩ完全であることを明らかにした．一方で２方向直交半直線交差グラフの同型問題は多項式時間で解けることが知られている．この成果をまとめ，論文誌に発表した．その他，３．上向き三角形グラフの認識アルゴリズムを改良し，この成果を国内会議で発表した．また，４．キャタピラの調和彩色数に関する考察と５．サブキュービックグラフに対するIrreversible 2-Conversion Set問題の計算量に関する成果を論文誌に発表した．

１．直交半直線交差木の特徴付け：直交半直線交差グラフは耐故障ナノ回路設計に関連して定義されたグラフの族であり，効率的なナノ回路設計のためにこのグラフの構造に関する研究が必要とされている．グラフの構造に関する研究で重要なのがグラフの特徴付けと認識問題の計算量である．直交半直線交差木とは，閉路を含まない直交半直線交差グラフであり，いわば最も単純な場合の直交半直線交差グラフである．今年度，この直交半直線交差木の特徴付けを示すと共に，その認識問題が線形時間で解けることを明らかにた．この成果をまとめ，論文誌に発表した．２．台形グラフの同型問題のＧＩ完全性：グラフ同型問題とは，入力として与えられた２つのグラフが同じかどうかを判定する問題である．台形グラフとは２本の水平線の間に張られた台形の集合によって定義される交差グラフであり，台形グラフの補グラフの族は２方向直交半直線交差グラフの族を真に含む．台形グラフの同型問題の計算量は１０年以上未解決問題であったが，今年度それがＧＩ完全であることを明らかにした．一方で２方向直交半直線交差グラフの同型問題は多項式時間で解けることが知られている．この成果をまとめ，論文誌に発表した．その他，３．上向き三角形グラフの認識アルゴリズムを改良し，この成果を国内会議で発表した．また，４．キャタピラの調和彩色数に関する考察と５．サブキュービックグラフに対するIrreversible 2-Conversion Set問題の計算量に関する成果を論文誌に発表した．