Zobrazeno 1 - 10
of 179
pro vyhledávání: '"Nederlof, Jesper"'
An arithmetic progression is a sequence of integers in which the difference between any two consecutive elements is the same. We investigate the parameterized complexity of two problems related to arithmetic progressions, called Cover by Arithmetic P
Externí odkaz:
http://arxiv.org/abs/2312.06393
Autor:
Nederlof, Jesper, Szilágyi, Krisztina
In this paper we investigate the parameterized complexity of the task of counting and detecting occurrences of small patterns in unit disk graphs: Given an $n$-vertex unit disk graph $G$ with an embedding of ply $p$ (that is, the graph is represented
Externí odkaz:
http://arxiv.org/abs/2312.06377
A homomorphism from a graph $G$ to a graph $H$ is an edge-preserving mapping from $V(G)$ to $V(H)$. In the graph homomorphism problem, denoted by $Hom(H)$, the graph $H$ is fixed and we need to determine if there exists a homomorphism from an instanc
Externí odkaz:
http://arxiv.org/abs/2312.03859
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
Finding a Hamiltonian cycle in a given graph is computationally challenging, and in general remains so even when one is further given one Hamiltonian cycle in the graph and asked to find another. In fact, no significantly faster algorithms are known
Externí odkaz:
http://arxiv.org/abs/2308.01574
Autor:
Chalermsook, Parinya, Fomin, Fedor, Hamm, Thekla, Korhonen, Tuukka, Nederlof, Jesper, Orgo, Ly
We prove the following result about approximating the maximum independent set in a graph. Informally, we show that any approximation algorithm with a ``non-trivial'' approximation ratio (as a function of the number of vertices of the input graph $G$)
Externí odkaz:
http://arxiv.org/abs/2307.01341
Autor:
Mannens, Isja, Nederlof, Jesper
We give a fine-grained classification of evaluating the Tutte polynomial $T(G;x,y)$ on all integer points on graphs with small treewidth and cutwidth. Specifically, we show for any point $(x,y) \in \mathbb{Z}^2$ that either - can be computed in polyn
Externí odkaz:
http://arxiv.org/abs/2307.01046
We show that there is no $2^{o(k^2)} n^{O(1)}$ time algorithm for Independent Set on $n$-vertex graphs with rank-width $k$, unless the Exponential Time Hypothesis (ETH) fails. Our lower bound matches the $2^{O(k^2)} n^{O(1)}$ time algorithm given by
Externí odkaz:
http://arxiv.org/abs/2210.02117
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
Publikováno v:
In Information and Computation October 2024 300