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