Zobrazeno 1 - 10
of 27
pro vyhledávání: '"Swennenhuis, Céline M. F."'
In the Steiner Tree problem we are given an undirected edge-weighted graph as input, along with a set $K$ of vertices called terminals. The task is to output a minimum-weight connected subgraph that spans all the terminals. The famous Dreyfus-Wagner
Externí odkaz:
http://arxiv.org/abs/2406.19819
We consider a 1-machine scheduling problem where the temperature of a job rises during processing, and cools down when not being processed according to given linear heating and cooling rates. No job's temperature is allowed to rise above a given thre
Externí odkaz:
http://arxiv.org/abs/2312.09683
In a classical scheduling problem, we are given a set of $n$ jobs of unit length along with precedence constraints, and the goal is to find a schedule of these jobs on $m$ identical machines that minimizes the makespan. Using the standard 3-field not
Externí odkaz:
http://arxiv.org/abs/2312.03495
In a classical scheduling problem, we are given a set of $n$ jobs of unit length along with precedence constraints and the goal is to find a schedule of these jobs on $m$ identical machines that minimizes the makespan. This problem is well-known to b
Externí odkaz:
http://arxiv.org/abs/2208.02664
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 number
Externí odkaz:
http://arxiv.org/abs/2106.15907
Let XNLP be the class of parameterized problems such that an instance of size n with parameter k can be solved nondeterministically in time $f(k)n^{O(1)}$ and space $f(k)\log(n)$ (for some computable function f). We give a wide variety of XNLP-comple
Externí odkaz:
http://arxiv.org/abs/2105.14882
The Isolation Lemma of Mulmuley, Vazirani and Vazirani [Combinatorica'87] provides a self-reduction scheme that allows one to assume that a given instance of a problem has a unique solution, provided a solution exists at all. Since its introduction,
Externí odkaz:
http://arxiv.org/abs/2105.01465
In the Bin Packing problem one is given $n$ items with weights $w_1,\ldots,w_n$ and $m$ bins with capacities $c_1,\ldots,c_m$. The goal is to find a partition of the items into sets $S_1,\ldots,S_m$ such that $w(S_j) \leq c_j$ for every bin $j$, wher
Externí odkaz:
http://arxiv.org/abs/2007.08204
For many algorithmic problems on graphs of treewidth $t$, a standard dynamic programming approach gives an algorithm with time and space complexity $2^{\mathcal{O}(t)}\cdot n^{\mathcal{O}(1)}$. It turns out that when one considers the more restrictiv
Externí odkaz:
http://arxiv.org/abs/2002.04368
Publikováno v:
SIAM Journal on Computing; 2023, Vol. 52 Issue 6, p1369-1412, 44p
