Mathematical Sciences: Combinatorial Investigation of Some Graph Optimization Problems

这项研究的重点是开发可用于设计有效的图包装、覆盖和识别问题的算法的分解技术。所要研究的特定图论问题在计算复杂性问题和计算机体系结构设计方面具有重要的实际应用。特别是，这项研究对并行进程的同步和计算机存储中的优化具有应用价值。给出了一般完全图上布局和覆盖问题的多项式时间算法。

This research focuses on the development of decomposition techniques which can be used in the design of efficient algorithms for graph packing, covering, and recognition problems. The specific graph theoretic problems to be investigated have important practical applications related to computational complexity issues and computer architecture design. In particular, the research has applications to the synchronization of parallel processes and to optimization in computer storage. Polynomial time algorithms for packing and covering problems on general perfect graphs are developed.