Results 1 to 10 of about 1,490 (139)
The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth [PDF]
SIAM Journal on Discrete Mathematics, 2016 In the Mixed Chinese Postman Problem (MCPP), given a weighted mixed graph G(it may have both edges and arcs), our aim is to nd a closed walk of minimum weight traversing each edge and arc at least once.
Magnus Wahlström
exaly +5 more sources
Improved Bounds for the Excluded-Minor Approximation of Treedepth [PDF]
SIAM Journal on Discrete Mathematics, 2019 Treedepth, a more restrictive graph width parameter than treewidth and pathwidth, plays a major role in the theory of sparse graph classes. We show that there exists a constant C such that for every integers a,b >= 2 and a graph G, if the treedepth of G ...
Czerwinski, Wojciech +2 more
core +6 more sources
Solving Connectivity Problems Parameterized by Treedepth in Single-Exponential Time and Polynomial Space [PDF]
, 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 ?^*(2^{?(twlog tw)}). Using their inspired Cut&Count technique, they obtained ?^*(
Hegerfeld, Falko, Kratsch, Stefan
core +5 more sources
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
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
Computing Shrub-Depth Decompositions [PDF]
, 2020 Shrub-depth is a width measure of graphs which, roughly speaking, corresponds to the smallest depth of a tree into which a graph can be encoded. It can be thought of as a low-depth variant of clique-width (or rank-width), similarly as treedepth is a low ...
, Kreutzer, Stephan
core +1 more source
Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming
Algorithms, 2018 Treedepth is a well-established width measure which has recently seen a resurgence of interest. Since graphs of bounded treedepth are more restricted than graphs of bounded tree- or pathwidth, we are interested in the algorithmic utility of this ...
Li-Hsuan Chen +3 more
doaj +1 more source
Parametrised Complexity of Model Checking and Satisfiability in Propositional Dependence Logic [PDF]
, 2020 In this paper, we initiate a systematic study of the parametrised complexity in the field of Dependence Logics which finds its origin in the Dependence Logic of V\"a\"an\"anen from 2007.
A Durand +22 more
core +3 more sources
Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey
Algorithms, 2019 Integer Linear Programming (ILP) is among the most successful and general paradigms for solving computationally intractable optimization problems in computer science.
Robert Ganian, Sebastian Ordyniak
doaj +1 more source
Game Comonads & Generalised Quantifiers [PDF]
Logical Methods in Computer ScienceGame comonads, introduced by Abramsky, Dawar and Wang and developed by Abramsky and Shah, give an interesting categorical semantics to some Spoiler-Duplicator games that are common in finite model theory. In particular they expose connections between one-
Adam Ó Conghaile, Anuj Dawar
doaj +1 more source