A Study of Approximation Algorithms for Graph Problems

图问题的逼近算法研究

• 批准号: 21500011
• 负责人: HIRATA Tomio
• 金额: $ 2.58万
• 依托单位: Nagoya University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21500011/
• 关键词: アルゴリズム理論; 近似アルゴリズム; アルゴリズム; 近似困難性; 2部クリーク; 2部クリーク被覆; 2部クリーク分割; 2クリーク分割; 独立集合

The purpose of this research is the design and analysis of approximation algorithms for the independent problem and the biclique covering(partitioning) problem of a graph. For the independent set problem, we proposed a notion of“weighted degree"of a vertex in a weighted graph, and gave approximation algorithms. We also gave an approximation algorithm for finding an independent set of a C_k-free graph. For the biclique covering problem, we proposed a method using a“set covering approach,"and for the biclique partition problem, we gave a formulation using the“exclusive rank"of a Boolean matrix. Furthermore, we discussed the approximation hardness of this problem.

本研究的目的是设计和分析图的独立问题和双簇覆盖（划分）问题的近似算法。对于独立集问题，我们提出了加权中顶点的“加权度”的概念。图，并给出了近似算法，用于寻找 C_k-free 图的独立集合，对于 biclique 覆盖问题，我们提出了一种使用“集合覆盖方法”的方法，并且对于biclique分配问题，我们给出了使用布尔矩阵的“排他性排序”的公式，此外，我们还讨论了该问题的近似难度。

项目成果

たて糸張力均一条件下における綜絖枠数最小化

在均匀经纱张力条件下最大限度地减少综框数量

• 发表时间: 2011
• 期刊: 電子情報通信学会コンピュテーション研究会技術報告
• 作者: 松浦勇;平田富夫
• 通讯作者: 平田富夫

A textile design and the Boolean rank problem

纺织品设计和布尔等级问题

• 发表时间: 2009
• 期刊: IADIS International Conference on Applied Computing
• 作者: I. Matsuura;M. Yagiura;T. Hirata
• 通讯作者: T. Hirata

A note on the greedy algorithm for finding independent sets of C_k-free graphs

关于寻找独立的无 C_k 图集的贪心算法的注解

• 发表时间: 2009
• 期刊: Information Processing Letters
• 影响因子: 0.5
• 作者: I. Koura;T. Ono;T. Hirata
• 通讯作者: T. Hirata

集合基底問題の正規基底を求めるヒューリスティックアルゴリズム

用于寻找集合基问题的正常基的启发式算法

• 发表时间: 2010
• 期刊: 情報処理学会アルゴリズム研究会資料
• 作者: 大月英明;平田富夫
• 通讯作者: 平田富夫

ドビー織機の綜絖枠数最小化問題に対する集合被覆アプローチ

解决多臂织机综框数量最小化问题的一套覆盖方法

• 发表时间: 2009
• 期刊: 情報処理学会論文誌
• 作者: 松浦勇;柳浦睦憲;平田富夫
• 通讯作者: 平田富夫