Combinatorial Graph Algorithms and Approximation

该项目将研究组合问题的算法和计算复杂性，重点是并行图算法和近似算法。除了更传统的np完全问题的多项式时间逼近领域外，还将特别关注NC算法获得的有效并行逼近。这种近似算法对P中的问题也很有意义。最大流量问题的p -完备性证明表明，流量的最低有效位数难以并行计算，但在NC（即快速并行算法）中是否能获得良好的近似是开放的。这将意味着二部匹配的确定性NC算法。研究了一种基于最小二乘近似的快速候选算法，并将其推广到更一般的线性规划问题。图同构问题的研究将主要通过研究仅涉及初等群论的组合算法的性能来继续；特别是，k元组着色算法的性能选择参数化类的图。

This project will study algorithms and computational complexity of combinatorial problems with an emphasis on parallel graph algorithms and approximation algorithms. Besides the more traditional area of polynomial time approximations to NP-complete problems, special attention will be given to efficient parallel approximations obtained by NC algorithms. Such approximation algorithms are of interest to problems in P too. The P-completeness proof of the maximum flow problem shows that the least significant digit of the flow is difficult to compute in parallel, but it is open whether good approximations could be obtained in NC (i.e., for fast parallel algorithms). This would imply a deterministic NC algorithm for bipartite matching. A seemingly fast candidate algorithm based on least squares approximations is investigated, and its extension to more general linear programming problems will be studied. The work on the graph isomorphism problem will continue mainly by investigating the performance of combinatorial algorithms involving only elementary group theory; in particular, the performance of the k-tuple coloring algorithm for selected parameterized classes of graphs.