权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Implementation and evaluation of graph approximation algorithms

图近似算法的实现和评估

基本信息

批准号：
16500008
负责人：
YAMAZAKI Koichi
金额：
$ 1.28万
依托单位：
Gunma University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2006
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-16500008/
关键词：
approximation algorithms volume respecting embeddings matroid covering problem bandwidth minimization problem d-claw free graphs independent set problem vertex boundary-width path distance-width Tree-length Branch-length Path-distance-

项目摘要

In this project, we have mainly implemented the following three approximation algorithms : From the experiments, we can conclude :・For bandwidth minimization problem we implemented an approximation algorithm based on volume respecting embeddings (VRE) method invented by U. Feige. For general graphs the experimental results of VRE is not better than that of GPS algorithm (Cuthill-Mckee method), however the results of VRE is significantly better than that of GPS algorithm for some special graph classes such as stretched complete bipartite graphs.・For several matroid covering problems we implemented approximation and heuristic algorithms. For cographic matroid covering problem, our proposed algorithm is comparable to a natural greedy algorithm. However for graphic and transversal matroid covering problems, the results of our proposed algorithm is inferior to that of natural greedy algorithms in quality. Our proposed algorithms can be implemented more easily than exact algorithms.・ For maximum weight independent set problem for d-claw free graphs several approximation algorithms are proposed. We implemented some of them ; SizeTwolmp introduced by V.Bafna et. al, Bestlmp proposed by B.Chandra et al., SquareImp developed by P.Berman and several algorithms of greedy type. The experimental results showed that SizeTwoImp, Bestlmp, and Squarelmp can find better solutions than greedy algorithms in reasonable time. The three approximation algorithms are practicable.Some theoretical results were obtained as a by-product through this research : Lower bounds of graph parameters called "vertex boundary-width" and "path distance-width". Vertex boundary-width can be considered as a lower bound of bandwidth and path distance-width is strongly related to approximating the bandwidth. We also obtained other theoretical results such as on unit grid intersection graphs, longest induced path problem for k-chordal graphs and tree-length. These are indirectly related to the research project.

在本项目中，我们主要实现了以下三种近似算法：通过实验，我们可以得出以下结论：·对于带宽最小化问题，我们实现了一种基于U·Feige提出的体积相关嵌入(VRE)方法的近似算法。对于一般的图，VRE的实验结果并不比GPS算法(Cuthill-McKee方法)好，但对于一些特殊的图类，如伸展的完全二部图，VRE的结果明显好于GPS算法。·对于几个拟阵覆盖问题，我们实现了逼近算法和启发式算法。对于共图拟阵覆盖问题，我们提出的算法与自然贪婪算法相当。然而，对于图和横截拟阵覆盖问题，我们提出的算法在质量上不如自然贪婪算法。我们提出的算法比精确算法更容易实现。·针对无d爪图的最大权独立集问题，提出了几种近似算法。我们实现了其中的一些；V.Bafna et.由B.Chandra等人提出的BestlMP算法，由P.Berman提出的SquareImp算法和几种贪婪类型的算法。实验结果表明，SizeTwoImp、BestlMP和Squarelp算法能够在合理的时间内找到比贪婪算法更好的解。这三种近似算法都是实用的，通过本研究得到了一些理论结果：称为“顶点边界宽度”和“路径距离宽度”的图参数下界。顶点边界宽度可以被认为是带宽的下界，路径距离宽度与带宽的近似密切相关。我们还得到了关于单位格交图、k弦图的最长诱导路问题和树的长度等理论结果。这些都与研究项目有间接的关系。