Paw图–边删除问题的线性顶点核心化算法

摘要： 图边删除问题中一类重要问题是研究是否可以删除图中不超过k条边之后使得剩余的图不存在某个子图结构H,而子图H为顶点个数不超过4的连通图的情况被研究得最为广泛.本文主要考虑H为Paw图(三角形其中一个顶点再邻接一条边)的情况,称为Paw图–边删除问题,并为该问题设计了一个32k个顶点的问题核.这是该问题的第1个线性顶点大小的问题核.文中主要的技术是结合两个新的皇冠分解的变体来分析图... （共16页）