论文部分内容阅读
本文介绍了一类普通的组合优化问题一顶点覆盖。在以前的学习中碰到只是一种最小顶点覆盖，即在无向图G=(V,E)中选择尽可能少的点使其覆盖所有的边。在本文里将讨论另一类顶点覆盖一最大顶点覆盖，即在无向图G=(V,E)中，给定非负整数k，k≤|V|，在G中选择k个点，使其覆盖的边数尽可能的多。鉴于最大顶点覆盖问题也是NP-hard的，除非P=NP，否则不可能在多项式时间内找到最优的算法。考虑一种特殊的图形一树，针对该图形设计一些近似算法，并分析其性能。全文共分为三个章节：
第一章是引言部分，介绍了组合优化和算法的一些概念和基本知识。
第二章主要介绍了比较熟悉的最小顶点覆盖问题，关于该问题有一些著名的结论和成果，给出了一些介绍。
第三章是本文的主要部分，详细讨论了树上的最大顶点覆盖问题，基于贪婪算法的思想，给出了两个算法，第一个算法称为Fully Greedy，其近似比为2，第二个算法称为Dynamic Greedy，其近似比为4/3。