Few induced disjoint paths for H-free graphs

Autor: Martin, Barnaby, Paulusma, Daniël, Smith, Siani, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, Algorithms and Complexity

Publikováno v: Theoretical Computer Science, 939, 182. Elsevier
Theoretical Computer Science, 2022, Vol.939, pp.182-193 [Peer Reviewed Journal]

Paths $P^1,\ldots,P^k$ in a graph $G=(V,E)$ are mutually induced if any two distinct $P^i$ and $P^j$ have neither common vertices nor adjacent vertices. For a fixed integer $k$, the $k$-Induced Disjoint Paths problem is to decide if a graph $G$ with

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::50438cf6a3ffb99a5ebae4fcc57130cd
https://dspace.library.uu.nl/handle/1874/426588

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Induced Disjoint Paths in AT-free graphs

Autor: Golovach, Petr A., Paulusma, Daniël, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, Algorithms and Complexity

Publikováno v: Journal of Computer and System Sciences, 124, 170. Academic Press Inc.
Journal of computer and system sciences, 2022, Vol.124, pp.170-191 [Peer Reviewed Journal]

Paths $P_1,\ldots,P_k$ in a graph $G=(V,E)$ are mutually induced if any two distinct $P_i$ and $P_j$ have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to decide if a graph $G

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2b35e301d0774a11d3f5d5b2034c4139
https://doi.org/10.1016/j.jcss.2021.10.003

Independence and Efficient Domination on P 6 -free Graphs

Autor: Lokshtanov, Daniel, Pilipczuk, Marcin, Leeuwen, Erik Jan van, Sub Algorithms and Complexity, Algorithms and Complexity

Publikováno v: ACM Transactions on Algorithms, 14(1). Association for Computing Machinery (ACM)

In the M aximum W eight I ndependent S et problem, the input is a graph G , every vertex has a non-negative integer weight, and the task is to find a set S of pairwise nonadjacent vertices, maximizing the total weight of the vertices in S . We give a

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c94ad2813a6999b6667c005d220084cd
https://doi.org/10.1145/3147214

Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices

Autor: Nederlof, Jesper, Fomin, Fedor V., Kratsch, Stefan, Leeuwen, Erik Jan van

We survey a number of recent results that relate the fine-grained complexity of several NP-Hard problems with the rank of certain matrices. The main technical theme is that for a wide variety of Divide & Conquer algorithms, structural insights on ass

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=od_______101::72fc6684be468829ad7172d6d5a6ec5a
https://dspace.library.uu.nl/handle/1874/414803