Mark de Berg,Joachim Gudmundsson,Ali D Mehrabi
Mark de Berg
We study the following problem: preprocess a set O of objects into a data structure that allows us to efficiently report all pairs of objects from O that intersect inside an axis-aligned query range Q . We present data structures of size O ...
On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems [0.03%]
关于几种众所周知的系统发育网络问题的无根和根不确定变体的研究
Leo van Iersel,Steven Kelk,Georgios Stamoulis et al.
Leo van Iersel et al.
The hybridization number problem requires us to embed a set of binary rooted phylogenetic trees into a binary rooted phylogenetic network such that the number of nodes with indegree two is minimized. However, from a biological point of view...
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...