Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity [0.03%]
重温树形包装：更快的完全动态最小割和树木度量算法
Tijn de Vos,Aleksander Christiansen
Tijn de Vos
Tree-packings - collections of spanning trees of a graph - are a fundamental tool in the study of minimum cut and related graph parameters. They have played a central role in the design of algorithms across static, dynamic, and distributed ...
A General Upper Bound for the Runtime of a Coevolutionary Algorithm on Impartial Combinatorial Games [0.03%]
协同进化算法在公正组合博弈上的运行时间的一般上限估算
Alistair Benford,Per Kristian Lehre
Alistair Benford
Due to their complex dynamics, combinatorial games are a key test case and application for algorithms that train game playing agents. Among those algorithms that train using self-play are coevolutionary algorithms (CoEAs). However, the succ...
Marten Folkertsma,Ian Mertz,Florian Speelman et al.
Marten Folkertsma et al.
A catalytic machine is a model of computation where a traditional space-bounded machine is augmented with an additional, significantly larger, "catalytic" tape, which, while being available as a work tape, has the caveat of being initialize...
Parameterized Complexities of Dominating and Independent Set Reconfiguration [0.03%]
图的支配集和独立集再定义问题的参数复杂性分析
Hans L Bodlaender,Carla Groenland,Céline M F Swennenhuis
Hans L Bodlaender
We settle the parameterized complexities of several variants of independent set reconfiguration and dominating set reconfiguration, parameterized by the number of tokens. We show that both problems are XL-complete when there is no limit on ...
The SLO Hierarchy of Pseudo-Boolean Functions and Runtime of Evolutionary Algorithms [0.03%]
伪布尔函数的SLO层次结构及进化算法的运行时间
Duc-Cuong Dang,Per Kristian Lehre
Duc-Cuong Dang
While some common fitness landscape characteristics are critical when determining the runtime of evolutionary algorithms (EAs), the relationship between fitness landscape structure and the runtime of EAs is poorly understood. Recently, Dang...
From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem [0.03%]
从数据补全到超立方体问题：独立集问题的参数化分析
Eduard Eiben,Robert Ganian,Iyad Kanj et al.
Eduard Eiben et al.
Several works have recently investigated the parameterized complexity of data completion problems, motivated by their applications in machine learning, and clustering in particular. Interestingly, these problems can be equivalently formulat...
A Clique-Based Separator for Intersection Graphs of Geodesic Disks in [Formula: see text] [0.03%]
基于盘状 clique 的 [Formula: see text] 中 geodesic 盘交图的分割点算法
Boris Aronov,Mark de Berg,Leonidas Theocharous
Boris Aronov
Let d be a (well-behaved) shortest-path metric defined on a path-connected subset of [Formula: see text] and let [Formula: see text] be a set of geodesic disks with respect to the metric d. We prove that [Formula: see text], the intersectio...
Smoothed Analysis of the 2-Opt Heuristic for the TSP under Gaussian Noise [0.03%]
具高斯噪声TSP的2-opt启发式算法的平滑分析
Marvin Künnemann,Bodo Manthey,Rianne Veenstra
Marvin Künnemann
The 2-opt heuristic is a very simple local search heuristic for the traveling salesperson problem. In practice it usually converges quickly to solutions within a few percentages of optimality. In contrast to this, its running-time is expone...
On the Parameterized Complexity of Eulerian Strong Component Arc Deletion [0.03%]
欧拉强分量弧删除问题的参数复杂度分析
Václav Blažej,Satyabrata Jana,M S Ramanujan et al.
Václav Blažej et al.
In this paper, we study the Eulerian Strong Component Arc Deletion problem, where the input is a directed multigraph and the goal is to delete the minimum number of arcs to ensure every strongly connected component of the resulting digraph ...
ShockHash: Near Optimal-Space Minimal Perfect Hashing Beyond Brute-Force [0.03%]
ShockHash：超越蛮力的几乎最优空间最小完美哈希算法
Hans-Peter Lehmann,Peter Sanders,Stefan Walzer
Hans-Peter Lehmann
A minimal perfect hash function (MPHF) maps a set S of n keys to the first n integers without collisions. There is a lower bound of n log 2 e - O ( log n ) ≈ 1.44 n bits needed to represent an MPHF. This can be reached by a brute-for...