Results 101 to 110 of about 147 (114)
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 +3 more sources
Some of the next articles are maybe not open access.
Related searches:
Related searches:
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 ...
Jeremy Kun, Blair D Sullivan
exaly +3 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 +2 more sources
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{
Gregory Gutin, Magnus Wahlstrom
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 +2 more sources
Distributed Model Checking on Graphs of Bounded Treedepth
AlgorithmicaAbstract We establish that every monadic second-order logic (MSO) formula on graphs with bounded treedepth is decidable in a constant number of rounds within the model. To our knowledge, this marks the first meta-theorem regarding distributed model checking. Various optimization problems on graphs are expressible
Fedor V Fomin +2 more
exaly +5 more sources
Approximation Algorithms for Treewidth, Pathwidth, and Treedepth—A Short Survey
Lecture Notes in Computer ScienceThis short survey discusses old and new approximation algorithms for treewidth, and for the related parameters pathwidth and treedepth.
Hans L Bodlaender, Bodlaender Hans L
exaly +3 more sources
A graph searching game for block treedepth and a cubic kernel by vertex cover
Theoretical Computer SciencezbMATH Open Web Interface contents unavailable due to conflicting licenses.
Archontia C Giannopoulou +1 more
exaly +4 more sources
Computing Twin-Width via Treedepth and Vertex Integrity.
Twin-width is a graph parameter that has become central to explaining the fixed-parameter tractability of first-order model checking across many graph classes. Despite its algorithmic importance, computing twin-width remains poorly understood: even recognizing graphs of twin-width at most four is NP-hard, and no fixed-parameter approximations ...Ganian, Robert, Rocton, Mathis
openaire +2 more sources
Exploring the gap between treedepth and vertex cover through vertex integrity
Theoretical Computer Science, 2022Tatsuya Gima +2 more
exaly