平面图团覆盖问题：核心化与参数化算法优化

平面图团覆盖问题的核心化和参数化算法是一篇发表于2011年12月的武汉大学学报(理学版)的研究论文，由张文块和Rudolf Fleischer共同完成。该论文针对经典的理论计算问题——团覆盖问题，从参数理论的角度出发，提出了一种核心化简化规则。团覆盖问题旨在寻找在无向图中覆盖所有边的最小团集合，其实际应用广泛，吸引了学术界的持续关注。 论文的核心贡献在于，作者通过核心化技术，将原问题简化为规模为4k-4的问题核心，这里的k表示参数，核心化后的规模显著减小。这种核心化方法允许使用复杂度为(20k+n^2)的参数化算法来求解平面图团覆盖问题的精确解，相比于传统的启发式算法，这种方法具有更高的精确性和时间效率。 核心化的基本思想是利用特定的简化规则，将原问题实例缩小到一个称为“核心”的小型子问题，这个核心可能与参数k的关系是线性的、多项式的或者非多项式的。由于核心规模的大幅减小，即使使用穷举等基本算法也能在合理时间内找到解决方案。 此外，论文还提到了先前的研究者如Kellerman、KOU、Rajagopalan、Piepho和Gramm等人对团覆盖问题的贡献，他们设计了多项式时间复杂度的启发式算法。然而，Gramm等人在此基础上进一步探讨了普通图上团覆盖问题的核心化和参数化算法，提出了一系列简化规则，使得问题的核心规模降到了γ，这对于优化问题求解具有重要意义。 这篇论文不仅深化了对平面图团覆盖问题的理解，还提供了一种有效的方法来处理这类问题，为理论计算和实际应用提供了新的工具和技术。