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.