Zobrazeno 1 - 10
of 229
pro vyhledávání: '"van Leeuwen, Erik"'
The intensively studied Diameter problem is to find the diameter of a given connected graph. We investigate, for the first time in a structured manner, the complexity of Diameter for H-free graphs, that is, graphs that do not contain a fixed graph H
Externí odkaz:
http://arxiv.org/abs/2402.16678
Autor:
Kisfaludi-Bak, Sándor, Masaříková, Jana, van Leeuwen, Erik Jan, Walczak, Bartosz, Węgrzycki, Karol
The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree. Hence, it is intuitively similar to treewidth, but the measures are formally incomparable. Motivated by the broad study of algorithms and separators on pl
Externí odkaz:
http://arxiv.org/abs/2310.11283
Autor:
Bodlaender, Hans L., Mannens, Isja, Oostveen, Jelle J., Pandey, Sukanya, van Leeuwen, Erik Jan
The Integer Multicommodity Flow problem has been studied extensively in the literature. However, from a parameterised perspective, mostly special cases, such as the Disjoint Paths problem, have been considered. Therefore, we investigate the parameter
Externí odkaz:
http://arxiv.org/abs/2310.05784
We consider a natural generalization of Vertex Cover: the Subset Vertex Cover problem, which is to decide for a graph $G=(V,E)$, a subset $T \subseteq V$ and integer $k$, if $V$ has a subset $S$ of size at most $k$, such that $S$ contains at least on
Externí odkaz:
http://arxiv.org/abs/2307.05701
Autor:
Bergougnoux, Benjamin, Chekan, Vera, Ganian, Robert, Kanté, Mamadou Moustapha, Mnich, Matthias, Oum, Sang-il, Pilipczuk, Michał, van Leeuwen, Erik Jan
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space
Externí odkaz:
http://arxiv.org/abs/2307.01285
Autor:
Bodlaender, Hans L., Johnson, Matthew, Martin, Barnaby, Oostveen, Jelle J., Pandey, Sukanya, Paulusma, Daniel, Smith, Siani, van Leeuwen, Erik Jan
We study Steiner Forest on $H$-subgraph-free graphs, that is, graphs that do not contain some fixed graph $H$ as a (not necessarily induced) subgraph. We are motivated by a recent framework that completely characterizes the complexity of many problem
Externí odkaz:
http://arxiv.org/abs/2305.01613
Autor:
Johnson, Matthew, Martin, Barnaby, Pandey, Sukanya, Paulusma, Daniël, Smith, Siani, van Leeuwen, Erik Jan
For any finite set $\mathcal{H} = \{H_1,\ldots,H_p\}$ of graphs, a graph is $\mathcal{H}$-subgraph-free if it does not contain any of $H_1,\ldots,H_p$ as a subgraph. In recent work, meta-classifications have been studied: these show that if graph pro
Externí odkaz:
http://arxiv.org/abs/2305.01104
Autor:
Lozin, Vadim, Martin, Barnaby, Pandey, Sukanya, Paulusma, Daniel, Siggers, Mark, Smith, Siani, van Leeuwen, Erik Jan
For a fixed set ${\cal H}$ of graphs, a graph $G$ is ${\cal H}$-subgraph-free if $G$ does not contain any $H \in {\cal H}$ as a (not necessarily induced) subgraph. A recently proposed framework gives a complete classification on ${\cal H}$-subgraph-f
Externí odkaz:
http://arxiv.org/abs/2211.14214
Autor:
Johnson, Matthew, Martin, Barnaby, Oostveen, Jelle J., Pandey, Sukanya, Paulusma, Daniël, Smith, Siani, van Leeuwen, Erik Jan
For any particular class of graphs, algorithms for computational problems restricted to the class often rely on structural properties that depend on the specific problem at hand. This begs the question if a large set of such results can be explained
Externí odkaz:
http://arxiv.org/abs/2211.12887
Autor:
Johnson, Matthew, Martin, Barnaby, Smith, Siani, Pandey, Sukanya, Paulusma, Daniel, van Leeuwen, Erik Jan
We show that Edge Multiway Cut (also called Multiterminal Cut) and Node Multiway Cut are NP-complete on graphs of maximum degree $3$ (also known as subcubic graphs). This improves on a previous degree bound of $11$. Our NP-completeness result holds e
Externí odkaz:
http://arxiv.org/abs/2211.12203