图的团横贯问题的算法和复杂性

在图论中，图的横贯是一类重要概念，它既是超图横贯概念的一类特例，又涵盖了图论中的众多重要概念，如覆盖、团覆盖、弱染色、控制集和全控制集等，在计算机、通信网络的设计和选址问题中具有广泛的应用。本项目研究图的团横贯和团独立集问题的算法复杂性和极值问题。由于该类问题已被证明是NP-困难的，因此下列工作有着重要的研究价值：该类问题近似算法的设计与分析；重要网络图类上该类问题多项式时间算法的设计与分析；所对应图参数的界的估计和极值问题研究。算法复杂性和近似算法的研究是理论计算机科学和组合优化的重要任务之一，本项目的研究正是基于上述目标和任务，力图推进国内图论、理论计算机和组合优化的结合研究。