Algorithm design techniques based on transformation into network structure

基于网络结构转化的算法设计技术

• 批准号: 23500015
• 负责人: NAGAMOCHI Hiroshi
• 金额: $ 3.24万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23500015/
• 关键词: 数理工学; 計算機科学; グラフ理論; 離散最適化; 厳密解法; 計算量解析; 近似解法; アルゴリズム; 列挙法

Our aim is to design algorithms for discrete optimization problems with graph structure. We have obtained approximation algorithms and exact algorithms for several NP-hard but important problems such as the maximum independent set problem.We have theoretically analyzed the approximation ratios of our approximation algorithms and derived upper bounds on the time complexities of our exact algorithms.In particular, for designing exact algorithms, we have devised new design techniques such as amortization by shifts, decomposition by cut-pairs,and how to compute the largest root of a set of recursive equations.

我们的目标是用图来设计离散优化问题的算法 结构我们得到了几个NP难问题的近似算法和精确算法， 本文对最大独立集问题等重要问题进行了研究，从理论上分析了近似算法的近似比，导出了精确算法时间复杂度的上界，特别是在设计精确算法方面，提出了移位摊销、割对分解、递归方程组最大根的计算等新的设计方法。

项目成果

An FPT algorithm for edge subset feedback edge set

边缘子集反馈边缘集的FPT算法

• DOI: 10.1016/j.ipl.2011.10.007
• 发表时间: 2012
• 期刊: INFORMATION PROCESSING LETTERS
• 影响因子: 0.5
• 作者: Xiao, Mingyu;Nagamochi, Hiroshi
• 通讯作者: Nagamochi, Hiroshi

Improved bounds for minimum fault-tolerant gossip graphs

改进了最小容错八卦图的界限

• 发表时间: 2011
• 作者: T. Hasunuma;H. Nagamochi
• 通讯作者: H. Nagamochi

Heuristics for a repetitive routing problem of a single grasp-and-delivery robot with an asymmetric edge cost function

具有不对称边缘成本函数的单个抓取和交付机器人的重复路由问题的启发式

• 发表时间: 2011
• 作者: A. Shurbevski;H. Nagamochi ;Y. Karuno
• 通讯作者: Y. Karuno

Characterizing Mechanisms in Obnoxious Facility Game

• DOI: 10.1007/978-3-642-31770-5_27
• 发表时间: 2012-08
• 作者: Ken Ibara;H. Nagamochi

An improved exact algorithm for undirected feedback vertex set

• DOI: 10.1007/s10878-014-9737-x
• 发表时间: 2013-12
• 期刊: Journal of Combinatorial Optimization
• 影响因子: 1
• 作者: Mingyu Xiao;H. Nagamochi