Results 41 to 50 of about 147 (114)
Treedepth Parameterized by Vertex Cover Number.
, 2017 To solve hard graph problems from the parameterized perspective, structural parameters have commonly been used. In particular, vertex cover number is frequently used in this context. In this paper, we study the problem of computing the treedepth of a given graph G.
Yasuaki Kobayashi, Hisao Tamaki
openaire +3 more sources
Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters
, 2022 We investigate the parameterized complexity of Binary CSP parameterized by the vertex cover number and the treedepth of the constraint graph, as well as by a selection of related modulator-based parameters. The main findings are as follows: i) Binary CSP parameterized by the vertex cover number is $\mathrm{W}[3]$-complete.
Bodlaender, Hans L. +2 more
openaire +6 more sources
Weighted Treedepth is NP-complete on Graphs of Bounded Degree
CoRRA treedepth decomposition of an undirected graph $G$ is a rooted forest $F$ on the vertex set of $G$ such that every edge $uv\in E(G)$ is in ancestor-descendant relationship in $F$. Given a weight function $w\colon V(G)\rightarrow \mathbb{N}$, the weighted depth of a treedepth decomposition is the maximum weight of any path from the root to a leaf ...
Jona Dirks +3 more
openaire +2 more sources
About Treedepth and Related Notions
, 2017 Dissertation, RWTH Aachen University, 2017; Aachen 1 Online-Ressource (getrennte Zählung) : Illustrationen (2017).
openaire +2 more sources
Reconfiguration in bounded bandwidth and tree-depth [PDF]
Journal of Computer and System Sciences, 2018 We show that several reconfiguration problems known to be PSPACE-complete remain so even when limited to graphs of bounded bandwidth. The essential step is noticing the similarity to very limited string rewriting systems, whose ability to directly simulate Turing Machines is classically known.
openaire +4 more sources
PACE Solver Description: Computing Exact Treedepth via Minimal Separators.
, 2020 This is a description of team xuzijian629’s treedepth solver submitted to PACE 2020. As we use a top-down approach, we enumerate all possible minimal separators at each step. The enumeration is sped up by several novel pruning techniques and is based on our conjecture that we can always have an optimal decomposition without using separators with size ...
Xu, Zijian +2 more
openaire +3 more sources
Local search for valued constraint satisfaction parameterized by treedepth
CoRR7 ...
openaire +2 more sources
PACE Solver Description: Bute-Plus: A Bottom-Up Exact Solver for Treedepth
, 2020 This note introduces Bute-Plus, an exact solver for the treedepth problem. The core of the solver is a positive-instance driven dynamic program that constructs an elimination tree of minimum depth in a bottom-up fashion. Three features greatly improve the algorithm's run time. The first of these is a specialised trie data structure.
openaire +4 more sources
DAIA: a decompose and improve algorithm for treedepth decomposition
, 2020 DAIA is a two-phases heuristic algorithm that searches for good treedepth decompositions of graphs. First it builds a treedepth decomposition partitionning recursively the vertices. Then it modifies the resulting tree in order to reduce its height.
openaire +1 more source
A faster polynomial-space algorithm for Hamiltonian cycle parameterized by treedepth
CoRRA large number of NP-hard graph problems can be solved in $f(w)n^{O(1)}$ time and space when the input graph is provided together with a tree decomposition of width $w$, in many cases with a modest exponential dependence $f(w)$ on $w$. Moreover, assuming the Strong Exponential-Time Hypothesis (SETH) we have essentially matching lower bounds for many ...
openaire +2 more sources