Research on parameterized graph algorithms

参数化图算法研究

• 批准号: 21500007
• 负责人: TAKENAGA Yasuhiko
• 金额: $ 1.33万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21500007/
• 关键词: アルゴリズム; グラフ; 計算量; パラメータ化計算量; 頂点彩色問題

We have developed fixed-parameter algorithms or proved the hardness of vertex coloring problems on parameterized graphs obtained by adding or deleting edges from graphs in classes such as comparability graphs, permutation graphs and grid graphs. We have also developed a fixed-parameter algorithm for isomorphism of tree+ ke graphs. In addition, we have clarified the property of problems and parameterized graph classes which makes it possible to design fixed-parameter algorithms.

我们已经开发了固定参数的算法或证明的硬度的顶点着色问题的参数化图，通过添加或删除边的图类，如可比图，置换图和网格图。我们还发展了树+ ke图同构的固定参数算法。此外，我们还阐明了问题和参数化图类的性质，这使得设计固定参数算法成为可能。

项目成果

パラメータ化permutationグラフの頂点彩色問題

参数化排列图的顶点着色问题

• 发表时间: 2012
• 作者: 小寺諒;武永康彦
• 通讯作者: 武永康彦

パラメータ化グラフに対するFixed-Parameterアルゴリズムの設計手法

参数化图的固定参数算法设计方法

• 发表时间: 2010
• 作者: 岩永耕平;武永康彦
• 通讯作者: 武永康彦

Precoloring Extension on Grid Graphs

网格图上的预着色扩展

• 发表时间: 2010
• 作者: T.Ito;X.Zhou;T.Nishizeki;Yasuhiko Takenaga and Akihiro Yamada
• 通讯作者: Yasuhiko Takenaga and Akihiro Yamada

木+ keグラフの同型性判定問題

树+ke图同构判定问题

• 发表时间: 2012
• 作者: 上野豊;武永康彦
• 通讯作者: 武永康彦

比較可能-keグラフの頂点彩色問題のパラメータ化計算量

顶点着色问题的可比图参数化复杂度

• 发表时间: 2012
• 作者: 斉藤惇;武永康彦
• 通讯作者: 武永康彦