Combinatorial Graph Algorithms and Approximation

组合图算法和近似

• 批准号: 9218309
• 负责人: Martin Furer
• 金额: $ 10.2万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1993
• 资助国家: 美国
• 起止时间: 1993-04-15 至 1996-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9218309&HistoricalAwards=false
• 关键词: Combinatorial; Graph; Algorithms; 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.

这个项目将研究的算法和计算复杂性 组合问题，重点是并行图形算法， 近似算法 除了更传统的领域， NP完全问题的多项式时间近似，特殊 将注意力放在通过以下方法获得的有效并行近似上： NC算法 这种近似算法对P中的问题也很有意义。 的 最大流问题的P-完备性证明表明， 流的有效数字难以并行计算，但是 在NC中是否可以获得良好的近似是开放的（即， 用于快速并行算法）。 这意味着确定性NC 二分匹配算法 一个看似快速的候选算法 基于最小二乘逼近的方法， 更一般的线性规划问题将被研究。 关于图同构问题的工作将主要通过 研究组合算法的性能， 基本群论;特别是，k元组的性能 着色算法的选择参数类的图。