A Study of Reconfiguration Problems to Develop Dynamic Systems

开发动态系统的重构问题研究

• 批准号: 22700001
• 负责人: ITO Takehiro
• 金额: $ 2.33万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2010
• 资助国家: 日本
• 起止时间: 2010 至 2012
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22700001/
• 关键词: アルゴリズム理論; アルゴリズム; 近似困難性; 遷移可能性問題; L(2,1)ラベリング; グラフ; ナップザック問題; 部分集合和問題; グラフ分割問題; リスト辺彩色

In this research, we study problems of finding a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. In particular, we study such problems for knapsack problem, which is one of the most fundamental problems in theoretical computer science, and for graph partitioning problem with supply and demand, which has some applications to power delivery network. We first analyzed the computational hardness of these problems, and then gave approximationalgorithms. Our approximation algorithms are best possible from the viewpoint of approximation ratio.

在这项研究中，我们研究了在两个问题的两个可行解决方案之间找到逐步转换的问题，以使所有中间结果也是可行的。特别是，我们研究了背包问题的此类问题，这是理论计算机科学中最根本的问题之一，也是供需的图形分配问题，该问题在电力输送网络中有所应用。我们首先分析了这些问题的计算硬度，然后给出了近似值。从近似比的角度来看，我们的近似算法最好。

项目成果

An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree

树中列表边着色重新配置的改进充分条件

• DOI: 10.1587/transinf.e95.d.737
• 发表时间: 2012
• 期刊: IEICE Transactions on Information and Systems
• 影响因子: 0.7
• 作者: Takehiro Ito;Kazuto Kawamura and Xiao Zhou
• 通讯作者: Kazuto Kawamura and Xiao Zhou

On Disconnected Cuts and Separators

关于断开的切口和分隔符

• DOI: 10.1016/j.dam.2011.04.027
• 发表时间: 2011
• 期刊: Discrete Applied Mathematics
• 影响因子: 1.1
• 作者: Takehiro Ito;Marcin Kaminski;Daniel Paulusma and Dimitrios M. Thilikos
• 通讯作者: Daniel Paulusma and Dimitrios M. Thilikos

Approximability of the subset sum reconfiguration problem

• DOI: 10.1007/s10878-012-9562-z
• 发表时间: 2011-05
• 期刊: Journal of Combinatorial Optimization
• 影响因子: 1
• 作者: Takehiro Ito;E. Demaine

Parameterizing cut sets in a graph by the number of their components

• DOI: 10.1016/j.tcs.2011.07.005
• 发表时间: 2009-12
• 期刊: Theor. Comput. Sci.
• 作者: Takehiro Ito;M. Kaminski;D. Paulusma;D. Thilikos

On the complexity of reconfiguration problems

• DOI: 10.1016/j.tcs.2010.12.005
• 发表时间: 2011-03-18
• 期刊: THEORETICAL COMPUTER SCIENCE
• 影响因子: 1.1
• 作者: Ito, Takehiro;Demaine, Erik D.;Uno, Yushi
• 通讯作者: Uno, Yushi