Exact Algorithms for the Maximum Planar Subgraph Problem
Exact Algorithms for the Maximum Planar Subgraph Problem
复制标题
DOI：
10.1145/3320344
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Markus Chimani;Ivo Hedtke;Tilo Wiedera
中科院分区：
文献类型：
--
作者：
Markus Chimani;Ivo Hedtke;Tilo Wiedera
给定图 G，NP 困难最大平面子图问题要求 G 的平面子图具有最大边数。唯一已知的非平凡精确算法利用了 Kuratowski 著名的平面性准则，可以表示为整数线性规划 (ILP) 或伪布尔可满足性问题 (PBS)。我们研究了平面性的三种替代特征，了解它们对最大平面子图建模的适用性。对于每一种，我们都会考虑 ILP 和 PBS 变体，研究不同的配方方面，并评估它们的实际性能。
Given a graph G, the NP-hard Maximum Planar Subgraph problem asks for a planar subgraph of G with the maximum number of edges. The only known non-trivial exact algorithm utilizes Kuratowski’s famous planarity criterion and can be formulated as an integer linear program (ILP) or a pseudo-Boolean satisfiability problem (PBS). We examine three alternative characterizations of planarity regarding their applicability to model maximum planar subgraphs. For each, we consider both ILP and PBS variants, investigate diverse formulation aspects, and evaluate their practical performance.