Zobrazeno 1 - 10
of 3 228
pro vyhledávání: '"Jansen, A M"'
The NP-hard Odd Cycle Transversal problem asks for a minimum vertex set whose removal from an undirected input graph $G$ breaks all odd cycles, and thereby yields a bipartite graph. The problem is well-known to be fixed-parameter tractable when param
Externí odkaz:
http://arxiv.org/abs/2409.00245
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
For a fixed graph $H$, the $H$-SUBGRAPH HITTING problem consists in deleting the minimum number of vertices from an input graph to obtain a graph without any occurrence of $H$ as a subgraph. This problem can be seen as a generalization of VERTEX COVE
Externí odkaz:
http://arxiv.org/abs/2404.16695
For an optimization problem $\Pi$ on graphs whose solutions are vertex sets, a vertex $v$ is called $c$-essential for $\Pi$ if all solutions of size at most $c \cdot OPT$ contain $v$. Recent work showed that polynomial-time algorithms to detect $c$-e
Externí odkaz:
http://arxiv.org/abs/2404.09769
Autor:
Jansen, Bart M. P., Roy, Shivesh K.
We study a new graph separation problem called Multiway Near-Separator. Given an undirected graph $G$, integer $k$, and terminal set $T \subseteq V(G)$, it asks whether there is a vertex set $S \subseteq V(G) \setminus T$ of size at most $k$ such tha
Externí odkaz:
http://arxiv.org/abs/2310.04332
A kernelization for a parameterized decision problem $\mathcal{Q}$ is a polynomial-time preprocessing algorithm that reduces any parameterized instance $(x,k)$ into an instance $(x',k')$ whose size is bounded by a function of $k$ alone and which has
Externí odkaz:
http://arxiv.org/abs/2310.04303
The celebrated notion of important separators bounds the number of small $(S,T)$-separators in a graph which are 'farthest from $S$' in a technical sense. In this paper, we introduce a generalization of this powerful algorithmic primitive that is phr
Externí odkaz:
http://arxiv.org/abs/2309.11366
Autor:
Jansen, Bart M. P., Khazaliya, Liana, Kindermann, Philipp, Liotta, Giuseppe, Montecchiani, Fabrizio, Simonov, Kirill
Upward planarity testing and Rectilinear planarity testing are central problems in graph drawing. It is known that they are both NP-complete, but XP when parameterized by treewidth. In this paper we show that these two problems are W[1]-hard paramete
Externí odkaz:
http://arxiv.org/abs/2309.01264
The notion of $\mathcal{H}$-treewidth, where $\mathcal{H}$ is a hereditary graph class, was recently introduced as a generalization of the treewidth of an undirected graph. Roughly speaking, a graph of $\mathcal{H}$-treewidth at most $k$ can be decom
Externí odkaz:
http://arxiv.org/abs/2306.17065
Autor:
Munshi, S. C.1 (AUTHOR), Weggelaar-Jansen, A. M.2 (AUTHOR), van den Berg-Bakker, A.3 (AUTHOR), Blanchette, L. M. G.4 (AUTHOR), Harmsen van der Vliet-Torij, H. W.5 (AUTHOR), Hodes, M. W.6 (AUTHOR), van 't Hof, M.7 (AUTHOR), Lambregtse-van den Berg, M. P.8 (AUTHOR), van der Meer, L.1 (AUTHOR), Ernst-Smelt, H. E.1 (AUTHOR), Bijma, H. H.1 (AUTHOR) h.bijma@erasmusmc.nl
Publikováno v:
PLoS ONE. 10/31/2024, Vol. 19 Issue 10, p1-13. 13p.
