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

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

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

On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms

• DOI: 10.1007/s00453-012-9689-4
• 发表时间: 2011-08
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Kei Uchizawa;T. Aoki;Takehiro Ito;Akira Suzuki;Xiaoping Zhou