权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

組み合わせ最適化における指数サイズ・多項式時間近傍の設計

组合优化中指数大小和多项式时间邻域的设计

基本信息

批准号：
16092226
负责人：
玉木久夫
金额：
$ 7.3万
依托单位：
Meiji University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2007
项目状态：
已结题

项目摘要

指数サイズ・多項式時間近傍の設計の基礎となるグラフ分割アルゴリズムの研究を続け、成果を得た。平面グラフの分枝幅決定および分枝分割アルゴリズムの実装法についての実験を行い、種々の工夫を行うことによって従来の実装法では扱うことのできなかった大きさのグラフについても幅決定と分割構成ができることを確認した。また、平面グラフに対する刻み幅決定アルゴリズムを平面グラフよりも広いクラスに拡張するための研究を行い、進展を見た。拡張の基礎として、細部が公刊されていなかった、平面グラフのアルゴリズムの正当性の証明のある部分について、わかりやすい別証を構成した。この証明とそれに基づいた刻み幅決定アルゴリズムは、次のような平面上の描画を持つグラフのクラスに拡張できる見通しがついている(この部分については発表準備中)。(1)どの辺も高々一本の辺と交差する。(2)交差する辺をすべて取り除いてできる描画の各面において、取り除かれた辺は高々一対である。(3)交差の総数は定数以内である。また、近傍解法のハードウェア化の基礎として、ルックアップ表と算術分解にもとづいた論理回路の構成法の応用で成果を挙げた。

Exponential multivariate time proximity design is based on the division of research performance and the achievement of satisfactory results. In the plane, the branch width determines the division of the branch, the location of the branch, the size of the branch, the size of the branch, the width of the The plane, the surface, the surface, the plane, the plane, the plane The public journal, the department, the public journal, the public journal, the The frame of the image determines that the drawing on the plane is in the preparation of the table. (1) the number of students in the school will be higher than that of the other students. (2) the cross section should be divided into two parts, each side should be drawn, and the height should be high. (3) the number of intersections is within the fixed number. In this paper, the application of the near-vicinity method is introduced, and the results are used in the analysis of the operation of the circuit.

项目成果

期刊论文数量（42）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Optimal branch-decomposition of planar graphs in O(n3) Time

DOI：
10.1145/1367064.1367070
发表时间：
2005-07
期刊：
ACM Trans. Algorithms
影响因子：
0
作者：
Q. Gu;H. Tamaki
通讯作者：
Q. Gu;H. Tamaki

On Geometric Structure of Global Roundings for Graphs and Range Spaces

关于图和范围空间的全局舍入的几何结构

DOI：
发表时间：
2004
期刊：
Proc.of 9th Scandinavian Workshop on Algorithm Theory
影响因子：
0
作者：
T.Asano;N.Katoh;H.Tamaki;T.Tokuyama
通讯作者：
T.Tokuyama

Matching Algorithms Are Fast in Sparse Random Graphs

稀疏随机图中的匹配算法速度很快

DOI：
发表时间：
2004
期刊：
Proc.of the 21st Symposium on Theoretical Aspects of Computer Science (STACS04) LNCS2996
影响因子：
0
作者：
Holger Bast;Kurt Mehlhorn;Guido Schafer;Hisao Tamaki
通讯作者：
Hisao Tamaki

An FPGA design of AES encryption circuit with 128-bit key

128位密钥AES加密电路的FPGA设计