Zobrazeno 1 - 10
of 179
pro vyhledávání: '"Theory of computation → Parameterized complexity and exact algorithms"'
Publikováno v:
Theoretical Computer Science. 936:13-32
In a graph G = (V,E) with an edge coloring 𝓁:E → C and two distinguished vertices s and t, a colored (s,t)-cut is a set C̃ ⊆ C such that deleting all edges with some color c ∈ C̃ from G disconnects s and t. Motivated by applications in the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7fc5eddb6cac48a4f6ed047154cea6f8
https://doi.org/10.1016/j.tcs.2022.09.013
https://doi.org/10.1016/j.tcs.2022.09.013
Publikováno v:
Algorithmica.
For a non-negative integer $\ell$, a graph $G$ is an $\ell$-leaf power of a tree $T$ if $V(G)$ is equal to the set of leaves of $T$, and distinct vertices $v$ and $w$ of $G$ are adjacent if and only if the distance between $v$ and $w$ in $T$ is at mo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ae85473080b4236e5623599927b6f62b
https://doi.org/10.1007/s00453-023-01129-9
https://doi.org/10.1007/s00453-023-01129-9
Autor:
Włodarczyk, Michał
In Chordal/Interval Vertex Deletion we ask how many vertices one needs to remove from a graph to make it chordal (respectively: interval). We study these problems under the parameterization by treewidth $tw$ of the input graph $G$. On the one hand, w
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::246891775064f9c2c59588f76ec4f007
http://arxiv.org/abs/2305.03440
http://arxiv.org/abs/2305.03440
Publikováno v:
Algorithmica, 84(11), 3407-3458. Springer
Proceedings of the 16th International Symposium on Parameterized and Exact Computation, IPEC 2021
Proceedings of the 16th International Symposium on Parameterized and Exact Computation, IPEC 2021
In the ���-Minor-Free Deletion problem one is given an undirected graph G, an integer k, and the task is to determine whether there exists a vertex set S of size at most k, so that G-S contains no graph from the finite family ��� as a min
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::574791961fab792440da5735d78b9f90
https://research.tue.nl/nl/publications/037a5637-ffbf-478d-8d21-5ac08bbf35a2
https://research.tue.nl/nl/publications/037a5637-ffbf-478d-8d21-5ac08bbf35a2
Autor:
Kobayashi, Yasuaki, Otachi, Yota
Publikováno v:
Algorithmica. 84:2379-2393
Graph Burning asks, given a graph $G = (V,E)$ and an integer $k$, whether there exists $(b_{0},\dots,b_{k-1}) \in V^{k}$ such that every vertex in $G$ has distance at most $i$ from some $b_{i}$. This problem is known to be NP-complete even on connect
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::71558a9ef79d8bf93a9e536893d2746e
https://doi.org/10.1007/s00453-022-00962-8
https://doi.org/10.1007/s00453-022-00962-8
Autor:
V. Arvind, Venkatesan Guruswami
Publikováno v:
Algorithmica. 84:3276-3299
We introduce the problem of finding a satisfying assignment to a CNF formula that must further belong to a prescribed input subspace. Equivalent formulations of the problem include finding a point outside a union of subspaces (the Union-of-Subspace A
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2cc61fa0186886c0e2488144a69774b0
https://doi.org/10.1007/s00453-022-00958-4
https://doi.org/10.1007/s00453-022-00958-4
We provide a general framework to exclude parameterized running times of the form O(l^β + n^γ) for problems that have polynomial running time lower bounds under hypotheses from fine-grained complexity. Our framework is based on cross-compositions f
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::270f7302a4c97e8c21aea2716932e5bd
http://arxiv.org/abs/2301.00797
http://arxiv.org/abs/2301.00797
Autor:
Geerts, Floris, Vandevoort, Brecht
LIPIcs, Volume 255, ICDT 2023, Complete Volume
LIPIcs, Vol. 255, 26th International Conference on Database Theory (ICDT 2023), pages 1-466
LIPIcs, Vol. 255, 26th International Conference on Database Theory (ICDT 2023), pages 1-466
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::293fb00994779f2d5c23730505bad861
Maximum Parsimony is the problem of computing a most parsimonious phylogenetic tree for a taxa set X from character data for X. A common strategy to attack this notoriously hard problem is to perform a local search over the phylogenetic tree space. H
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::fadc8540795b93a69a19c7412ed35708
This report documents the program and outcomes of Dagstuhl Seminar 22381 "Rational Design of RiboNucleic Acids" (RNAs). The seminar covered a wide array of models, algorithmic strategies, molecular scales and modalities, all targeting in silico desig
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b60d8175266be21456fd0c5e3d9c93fe