论文标题
用结构参数化计算集团覆盖
Computing Clique Cover with Structural Parameterization
论文作者
论文摘要
大量的现实问题表现为覆盖图的边缘和/或顶点，并具有针对某些目标优化的集团。我们考虑了图形的不同结构参数，并设计了许多集团覆盖问题的固定参数可拖动算法。使用图表的集合表示，我们引入了一个用于计算具有不同目标的集团封面的框架。我们证明了用于各种集团涵盖问题的框架。我们的结果包括许多新算法，并在运行时间内进行了指数改进。
An abundance of real-world problems manifest as covering edges and/or vertices of a graph with cliques that are optimized for some objectives. We consider different structural parameters of graph, and design fixed-parameter tractable algorithms for a number of clique cover problems. Using a set representation of graph, we introduce a framework for computing clique cover with different objectives. We demonstrate use of the framework for a variety of clique cover problems. Our results include a number of new algorithms with exponential to double exponential improvements in the running time.
