Results 1 to 10 of about 299 (111)
Tight Bound on Treedepth in Terms of Pathwidth and Longest Path [PDF]
Combinatorica, 2023 We show that every graph with pathwidth strictly less than a that contains no path on 2b\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs ...
Marcin Pilipczuk +2 more
exaly +2 more sources
Distributed Model Checking on Graphs of Bounded Treedepth [PDF]
AlgorithmicaWe establish that every monadic second-order logic (MSO) formula on graphs with bounded treedepth is decidable in a constant number of rounds within the CONGEST model.
Pedro Montealegre +2 more
exaly +2 more sources
Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth [PDF]
Annual Conference for Computer Science Logic, 2023 We study the expressive power of first-order logic with counting quantifiers, especially the $k$-variable and quantifier-rank-$q$ fragment, using homomorphism indistinguishability.
Eva Fluck +2 more
semanticscholar +1 more source
Computing treedepth in polynomial space and linear fpt time [PDF]
Embedded Systems and Applications, 2022 The treedepth of a graph $G$ is the least possible depth of an elimination forest of $G$: a rooted forest on the same vertex set where every pair of vertices adjacent in $G$ is bound by the ancestor/descendant relation. We propose an algorithm that given
Wojciech Nadara +2 more
semanticscholar +1 more source
Treedepth vs Circumference [PDF]
Combinatorica, 2022 The circumference of a graph G is the length of a longest cycle in G , or $$+\infty $$ + ∞ if G has no cycle. Birmelé (J Graph Theory 43(1):24–25, 2003) showed that the treewidth of a graph G is at most its circumference minus 1.
Marcin Brianski +6 more
semanticscholar +1 more source
Recent Advances in Positive-Instance Driven Graph Searching
Algorithms, 2022 Research on the similarity of a graph to being a tree—called the treewidth of the graph—has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017).
Max Bannach, Sebastian Berndt
doaj +1 more source
Parameterized Algorithms for Queue Layouts
Journal of Graph Algorithms and Applications, 2022 An $h$-queue layout of a graph $G$ consists of a linear order of its vertices and a partition of its edges into $h$ sets, called queues, such that no two independent edges of the same queue nest.
Sujoy Bhore +3 more
doaj +1 more source
An Improved Time-Efficient Approximate Kernelization for Connected Treedepth Deletion Set [PDF]
arXiv.org, 2022 We study the CONNECTED \eta-TREEDEPTH DELETION problem where the input instance is an undireted graph G = (V, E) and an integer k. The objective is to decide if G has a set S \subseteq V(G) of at most k vertices such that G - S has treedepth at most \eta
E. Eiben +2 more
semanticscholar +1 more source
DynASP2.5: Dynamic Programming on Tree Decompositions in Action
Algorithms, 2021 Efficient exact parameterized algorithms are an active research area. Such algorithms exhibit a broad interest in the theoretical community. In the last few years, implementations for computing various parameters (parameter detection) have been ...
Johannes K. Fichte +3 more
doaj +1 more source
Solving connectivity problems parameterized by treedepth in single-exponential time and polynomial space [PDF]
Symposium on Theoretical Aspects of Computer Science, 2020 A breakthrough result of Cygan et al. (FOCS 2011) showed that connectivity problems parameterized by treewidth can be solved much faster than the previously best known time $\mathcal{O}^*(2^{\mathcal{O}(tw \log(tw))})$.
Falko Hegerfeld, Stefan Kratsch
semanticscholar +1 more source