论文标题
涡轮增压型较弱的启发式启发式
Turbocharging Heuristics for Weak Coloring Numbers
论文作者
论文摘要
有界的扩展和无处浓密的图表捕获了几种重要算法问题的理论障碍。这些图表可以以所谓的图形弱色数来表征，这些图形概括了众所周知的图形不变性变性（也称为k核号码）。作为NP-HARD，以前主要是通过增量启发式方法在现实世界图上计算出的弱色数。我们研究以指数级的子制作的启动时，在弱色数上所需的上限时会启动这种启发式方法。我们在相应的计算子问题上提供硬度和障碍结果。我们实施了几种由此产生的算法，并在先前研究的一组基准实例上表明它们具有竞争力，该实例包含86个图形，最高为183831个边缘。在超过一半的实例中，我们获得了改善的弱色数。
Bounded expansion and nowhere-dense classes of graphs capture the theoretical tractability for several important algorithmic problems. These classes of graphs can be characterized by the so-called weak coloring numbers of graphs, which generalize the well-known graph invariant degeneracy (also called k-core number). Being NP-hard, weak-coloring numbers were previously computed on real-world graphs mainly via incremental heuristics. We study whether it is feasible to augment such heuristics with exponential-time subprocedures that kick in when a desired upper bound on the weak coloring number is breached. We provide hardness and tractability results on the corresponding computational subproblems. We implemented several of the resulting algorithms and show them to be competitive with previous approaches on a previously studied set of benchmark instances containing 86 graphs with up to 183831 edges. We obtain improved weak coloring numbers for over half of the instances.
