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

容错纳米电路设计的正交半线交图研究

• 批准号: 14J08924
• 负责人: 髙岡 旭
• 金额: $ 1.22万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2014
• 资助国家: 日本
• 起止时间: 2014-04-25 至 2016-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14J08924/
• 关键词: グラフ理論; アルゴリズム論; 計算量理論; 応用離散数学; アルゴリズム; 計算量; 情報基礎; 離散数学

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

1. Direct semi-straight line differential wooden special payment: direct semi-straight line differential circuit design, and maintenance. The design of the circuit, the study of the equipment, the design of the circuit, the design, the design, the calculation, the calculation of the volume of calculation. This year, this year, the direct and semi-straight crossover system is in full swing. This year, the vertical and semi-straight cross-section special payment shows that there is a common understanding of the problem, and that the solution to the problem is in the form of a solution. The results of the review are reviewed, and the document table shows no. 2. The table of the table shows the completeness of the GI for the same type of problem: the same type of problem for each other. In the same way as in order to determine a problem in the same way as in order to determine the problem of the problem. The two-way half-straight intersection of the two-way straight-line intersection of the two-way straight line is really included. The calculation of the same type of problem has not been solved for more than 10 years. This year, the GI is fully aware that there is no need to improve the situation. One side of the two-way straight-line half-straight intersection, the same type of problem, multi-item time solution, multi-item time solution, multi-item time solution 4. The results of the calculation of the Irreversible 2-Conversion Set problem, the results of the calculation, the results, the table, the table.

项目成果

On Orthogonal Ray Trees

关于正交射线树

• 发表时间: 2014
• 作者: Asahi Takaoka;Satoshi Tayu;Shuichi Ueno
• 通讯作者: Shuichi Ueno

Graph Isomorphism Completeness for Trapezoid Graphs

梯形图的图同构完备性

• DOI: 10.1587/transfun.e98.a.1838
• 发表时间: 2015
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
• 作者: Irina Mustata;Kousuke Nishikawa;Asahi Takaoka;Satoshi Tayu;Shuichi Ueno;Asahi Takaoka
• 通讯作者: Asahi Takaoka

OBDD Representation of Intersection Graphs

交叉图的 OBDD 表示

• 发表时间: 2014
• 作者: Asahi Takaoka;Satoshi Tayu;Shuichi Ueno
• 通讯作者: Shuichi Ueno

Dominating Sets and Induced Matchings in Orthogonal Ray Graphs

正交射线图中的支配集和归纳匹配

• DOI: 10.1587/transinf.2014edp7184
• 发表时间: 2014
• 期刊: IEICE Transactions on Information and Systems
• 影响因子: 0.7
• 作者: Asahi Takaoka;Satoshi Tayu;and Shuichi Ueno
• 通讯作者: and Shuichi Ueno

上野研究室webページ

上野实验室网页