Design of Approximation Algorithms for the Problems with Grapth Structure

图结构问题的逼近算法设计

• 批准号: 16092212
• 负责人: NAGAMOCHI Hiroshi
• 金额: $ 4.42万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas
• 财政年份: 2004
• 资助国家: 日本
• 起止时间: 2004 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-16092212/
• 关键词: グラフアルゴリズム; 連結度; ネットワーク設計; 最適化; 配送スケジューリング; 近似アルゴリズム; パッキング; グラフ描画; 離散最適化; グラフ連結度; 図形パッキング; ファイアウォール高速化; 最長路問題; スケジューリング; 部分木被覆; パッキング問題; グラフのランキング; 分枝限定法; ミニマックス問題; 最小カット; グラフ分割; 機械スケジューリング

通信網, 電力網, 交通網, VLSIの配線, スケジューリング問題, 地理情報システム等の多くのシステム工学的, 情報工学的諸問題に対するアルゴリズムを設計する場合には, これらを離散最適化問題として定式化することで, 問題の持つ計算の複雑さの解明や高度な数学的解法の適用が可能となる. 本研究では, グラフアルゴリズムを中心的な道具として, 離散最適化問題に対する理論保証付きアルゴリズムの開発を行うとともにパッキング問題に対しては実際に難しい例題を効率よく解くソルバーの開発を行った.

Communications, power, transportation, VLSI wiring, communication, electrical engineering, transportation, electrical equipment, electrical engineering, electrical engineering, transportation, distribution, optimization, etc. It is possible to use the mathematical solution of height to solve the problem. In this study, we did a lot of research on the props and props of the center, and the theory of the optimization of the problem.

项目成果

On the one-sided crossing minimization in a bipartite graph with large degrees

大度二分图中的单边交叉最小化

• 发表时间: 2005
• 期刊: Theoretical Computer Science 332・1-3
• 作者: H.Nagamochi

Approximation algorithms for multicast routings in a network with multi-sources

多源网络中组播路由的近似算法

• 发表时间: 2007
• 期刊: IEICE Transactions on Fundamentals of Electro-nics, Communications and Computer Sciences 90-A
• 作者: E.;Morsy;H. Nagamochi;T. Hasunuma;T. Hasunuma;H. Nagamochi;H. Nagamochi;E. Morsy
• 通讯作者: E. Morsy

A 4/3-approximation for the minimum 2-local-vertex-connectivity augmentation in a connected graph

连通图中最小 2 局部顶点连通性增强的 4/3 近似

• 发表时间: 2005
• 期刊: J.Algorithms 56
• 作者: S.;Imahori;T. Hasunuma;H.Nagamochi;E. Morsy;H.Nagamochi;Y. Kamidoi;H. Nagamochi;H. Nagamochi;H. Nagamochi;H. Nagamochi;T.Ishii;H.Nagamochi;Y.Kamidoi;H.Nagamochi;H.Nagamochi;H.Nagamochi;P.Eades;T.Ishii;H.Nagamochi;H. Nagamochi;H. Nagamochi;H.Nagamochi;L.Zhao;H.Nagamochi;H.Nagamochi;H.Nagamochi;H.Nagamochi;石井利昌;H.Nagamochi;H.Nagamochi
• 通讯作者: H.Nagamochi

Performance analysis of a collision detection algorithm of spheres based on slab partitioning

基于slab划分的球体碰撞检测算法性能分析

• 发表时间: 2008
• 期刊: IEICE Transactions 91-A (9)
• 作者: T. Imamichi;H. Nagamochi
• 通讯作者: H. Nagamochi

Bi-criteria food packing by dynamic programming

通过动态规划的双标准食品包装

• 发表时间: 2007
• 期刊: J. Operations Research Society of Japan 50
• 作者: T. Fukunaga;H. Nagamochi;H. Nagamochi;T. Fukuanga;H. Nagamochi;Y. Karuno
• 通讯作者: Y. Karuno