Results 111 to 120 of about 467 (123)
Some of the next articles are maybe not open access.
A Heuristic Approach to the Treedepth Decomposition Problem for Large Graphs
Lecture Notes in Computer Science, 2021In this article, we describe algorithms and techniques used in the method ExTREEm for the treedepth decomposition problem. ExTREEm won the heuristic track of the 5th Parameterized Algorithms and Computational Experiments Challenge (PACE 2020). It searches for a minimum-height treedepth decomposition of a graph via computing graph separators.
Sylwester Swat, Marta Kasprzak
exaly +2 more sources
A Faster Parameterized Algorithm for Treedepth [PDF]
Lecture Notes in Computer Science, 2014 The width measure \emph{treedepth}, also known as vertex ranking, centered coloring and elimination tree height, is a well-established notion which has recently seen a resurgence of interest. We present an algorithm which---given as input an $n$-vertex graph, a tree decomposition of the graph of width $w$, and an integer $t$---decides Treedepth, i.e ...
Felix Reidl +2 more
exaly +4 more sources
Exploring the Gap Between Treedepth and Vertex Cover Through Vertex Integrity [PDF]
Lecture Notes in Computer Science, 2021 30 pages, 5 figures, CIAC ...
Tesshu Hanaka +2 more
exaly +3 more sources
On the size of minimal separators for treedepth decomposition
Discrete Applied MathematicsThe major changes from the first version are as follows. (1) The conjecture was resolved and the upper bound was slightly improved. (2) The experimental results were not correct and were removed. Specifically, there was a problem in the separator enumeration when we extended SMS [Korhonen 2020].
Vorapong Suppakitpaisarn
exaly +5 more sources
Compact representation of graphs with bounded bandwidth or treedepth
Information and Computation, 2022zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Shahin Kamali
exaly +3 more sources
Treedepth Bounds in Linear Colorings
Lecture Notes in Computer Science, 2018Low-treedepth colorings are an important tool for algorithms that exploit structure in classes of bounded expansion; they guarantee subgraphs that use few colors have bounded treedepth. These colorings have an implicit tradeoff between the total number of colors used and the treedepth bound, and prior empirical work suggests that the former dominates ...
Blair D Sullivan, Jeremy Kun
exaly +4 more sources
Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space [PDF]
SIAM Journal on Discrete Mathematics, 2023 For many algorithmic problems on graphs of treewidth t, a standard dynamic programming approach gives algorithms with time and space complexity 2 (*'-n ' K It turns out that when one considers the more restrictive parameter treedepth, it is often the ...
Michał Pilipczuk +2 more
exaly +1 more source
The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth
SIAM Journal on Discrete Mathematics, 2016Summary: In the mixed Chinese postman problem (MCPP), given a weighted mixed graph \(G\) (it may have both edges and arcs), our aim is to find a closed walk of minimum weight traversing each edge and arc at least once. The MCPP parameterized by the number of edges in \(G\) or the number of arcs in \(G\) is fixed-parameter tractable as proved by \textit{
Magnus Wahlstrom, Gregory Gutin
exaly +3 more sources
Compact Representation of Graphs with Small Bandwidth and Treedepth
2020 Data Compression Conference (DCC), 2020We consider the problem of compact representation of graphs with small bandwidth as well as graphs with small treedepth. These parameters capture structural properties of graphs that come in useful in certain applications. We present simple navigation oracles that support degree and adjacency queries in constant time and neighborhood query in constant ...
Shahin Kamali
exaly +3 more sources
Exploring the gap between treedepth and vertex cover through vertex integrity
Theoretical Computer Science, 2022Tesshu Hanaka +2 more
exaly