Heuristic algorithms with reasonable running time

具有合理运行时间的启发式算法

• 批准号: 20700003
• 负责人: ITO Takehiro
• 金额: $ 1.91万
• 依托单位: Tohoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2009
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20700003/
• 关键词: アルゴリズム理論; アルゴリズム; グラフ; 木; 部分k木; 分割問題

In this research, we obtained heuristic algorithms which runs in reasonable time from the viewpoint of practical applications. We dealt with two graph partition problems, called the power-supply problem and the uniform partition problem. For the power-supply problem, we gave an approximation algorithm, called an FPTAS. Based on the FPTAS, we also gave a heuristic algorithm. For the uniform partition problem, we gave a polynomial-time algorithm which finds an optimal solution for trees.

在这项研究中，我们获得了从实际应用的角度来看运行时间合理的启发式算法。我们处理了两个图划分问题，称为电源问题和均匀划分问题。对于电源问题，我们给出了一种近似算法，称为 FPTAS。基于FPTAS，我们还给出了启发式算法。对于均匀划分问题，我们给出了一种多项式时间算法，可以找到树的最优解。

项目成果

Reconfiguration of List Edge-Colorings in a Graph

重新配置图表中的列表边着色

• 发表时间: 2009
• 期刊: Lecture Notes in Computer Science Vol.5664
• 作者: Takehiro Ito;Marcin Kaminski;Erik D. Demaine
• 通讯作者: Erik D. 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

Partitioning a Weighted Tree to Subtrees of Almost Uniform Size

• DOI: 10.1007/978-3-540-92182-0_20
• 发表时间: 2008-12
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Takehiro Ito;T. Uno;Xiaoping Zhou;Takao Nishizeki

Partitioning graphs of supply and demand

• DOI: 10.1016/j.dam.2008.08.012
• 发表时间: 2005-05
• 期刊: 2005 IEEE International Symposium on Circuits and Systems
• 作者: Takehiro Ito;Xiao Zhou;Takao Nishizeki