Implementation and evaluation of graph approximation algorithms

在这个项目中，我们主要实现了以下三种接近算法：来自实验，我们可以概括：·为了带宽最小化问题，我们实现了基于体积尊重嵌入（VRE）方法的近似算法。Feige。就一般图而言，VRE的实验结果并不优于GPS算法（Cuthill-McKee方法）而言，但对于某些特殊图类的GPS算法而言，VRE的结果并不明显优于GPS算法（Cuthill-McKee方法）。对于一些基质覆盖的问题，我们实现了近似和启发性的算法。由于编码基质覆盖问题，我们提出的算法可以与自然贪婪的算法相比较。如何解决图形和跨基质覆盖问题，我们提出的算法的结果在质量中低于自然贪婪算法。我们提出的算法比实际算法更容易实现。对于d-claw无图形的最大权重独立设置问题已经提出了一些近似算法。我们实现了他们中的一些人;由V. Bafna等人介绍的SizeTwolmp。由B. Chandra等人提出的Bestlmp，SquareImp是由P. Berman开发的，以及贪婪类型的几种算法。实验结果显示，SizeTwoImp、Bestlmp和Squarelmp可以在合理的时间中找到比贪婪算法更好的解决方案。three approximation algorithms are practicable。一些theoretical results were obtained as a by-product through this research ：较低边界的图形参数called“vertex boundary-width”和“path distance-width”。垂直边界-宽度可以被认为是一个较低的带宽和路径距离的边界--宽度与接近带宽密切相关。我们还获得了其他的理论结果，如单元网格拼接图、K-和弦图和树长度最长的诱导路径问题。这些都与研究项目有直接关系。

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.