Combinatorial Graph Algorithms and Approximation

点击翻译按钮获取中文摘要

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.