Michał Włodarczyk
Michał Włodarczyk
We introduce the non-commutative subset convolution-a convolution of functions useful when working with determinant-based algorithms. In order to compute it efficiently, we take advantage of Clifford algebras, a generalization of quaternion...
Evangelos Bampas,Jurek Czyzowicz,Leszek Gąsieniec et al.
Evangelos Bampas et al.
Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on ...
Network Pollution Games [0.03%]
网络污染博弈
Eleftherios Anastasiadis,Xiaotie Deng,Piotr Krysta et al.
Eleftherios Anastasiadis et al.
The problem of pollution control has been mainly studied in the environmental economics literature where the methodology of game theory is applied for the pollution control. To the best of our knowledge this is the first time this problem i...
Arne Meier,Sebastian Ordyniak,M S Ramanujan et al.
Arne Meier et al.
In the present paper, we introduce the backdoor set approach into the field of temporal logic for the global fragment of linear temporal logic. We study the parameterized complexity of the satisfiability problem parameterized by the size of...
Complexity of Secure Sets [0.03%]
安全集的复杂性
Bernhard Bliem,Stefan Woltran
Bernhard Bliem
A secure set S in a graph is defined as a set of vertices such that for any X⊆S the majority of vertices in the neighborhood of X belongs to S. It is known that deciding whether a set S is secure in a graph is co-NP -complete. However...
Duc-Cuong Dang,Thomas Jansen,Per Kristian Lehre
Duc-Cuong Dang
Real-world optimisation problems are often dynamic. Previously good solutions must be updated or replaced due to changes in objectives and constraints. It is often claimed that evolutionary algorithms are particularly suitable for dynamic o...
Spin-the-bottle Sort and Annealing Sort: Oblivious Sorting via Round-robin Random Comparisons [0.03%]
旋转瓶排序与退火排序：轮流向量随机比较下的 oblivious 排序算法
Michael T Goodrich
Michael T Goodrich
We study sorting algorithms based on randomized round-robin comparisons. Specifically, we study Spin-the-bottle sort, where comparisons are unrestricted, and Annealing sort, where comparisons are restricted to a distance bounded by a temper...
Marek Cygan,Dániel Marx,Marcin Pilipczuk et al.
Marek Cygan et al.
We study a family of problems where the goal is to make a graph Eulerian, i.e., connected and with all the vertices having even degrees, by a minimum number of deletions. We completely classify the parameterized complexity of various versio...