Results 41 to 50 of about 147,152 (326)
The Burning Number of Directed Graphs: Bounds and Computational Complexity
Theory and Applications of Graphs, 2020 The burning number of a graph was recently introduced by Bonato et al. Although they mention that the burning number generalizes naturally to directed graphs, no further research on this has been done. Here, we introduce graph burning for directed graphs,
Remie Janssen
doaj +1 more source
Paradigms for Parameterized Enumeration [PDF]
, 2013 The aim of the paper is to examine the computational complexity and algorithmics of enumeration, the task to output all solutions of a given problem, from the point of view of parameterized complexity.
D. Marx +7 more
core +2 more sources
On the Parameterized Complexity of Reconfiguration Problems [PDF]
Algorithmica, 2013 We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration version of an optimization problem $Q$ takes as input two feasible solutions $S$ and $T$ and determines if there is a sequence of {\em reconfiguration steps} that can be applied to transform $S$ into $T$ such that each step results in a ...
Mouawad, Amer E. +4 more
openaire +2 more sources
On the Parameterized Complexity of Pooling Design [PDF]
Journal of Computational Biology, 2009 Pooling design is a very helpful tool for reducing the number of tests in DNA library screening, which is a key process to obtain high-quality DNA libraries for studying gene functions. Three basic problems in pooling design are, given an m x n binary matrix and a positive integer d, to decide whether the matrix is d-separable (d-separable, or d ...
Yongxi, Cheng +3 more
openaire +2 more sources
Treewidth-based algorithms for the small parsimony problem on networks
Algorithms for Molecular Biology, 2022 Background Phylogenetic reconstruction is one of the paramount challenges of contemporary bioinformatics. A subtask of existing tree reconstruction algorithms is modeled by the Small Parsimony problem: given a tree T and an assignment of character-states
Celine Scornavacca, Mathias Weller
doaj +1 more source
On the Parameterized Complexity of Consensus Clustering [PDF]
Theoretical Computer Science, 2011 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Dörnfelder, Martin +3 more
openaire +2 more sources
The Complexity of Reachability in Affine Vector Addition Systems with States [PDF]
Logical Methods in Computer Science, 2021 Vector addition systems with states (VASS) are widely used for the formal verification of concurrent systems. Given their tremendous computational complexity, practical approaches have relied on techniques such as reachability relaxations, e.g., allowing
Michael Blondin, Mikhail Raskin
doaj +1 more source
The Parameterized Complexity of Positional Games [PDF]
, 2017 To appear in the Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Bonnet, Edouard +4 more
openaire +5 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
The Parameterized Complexity of the Equidomination Problem [PDF]
, 2017 A graph $G=(V,E)$ is called equidominating if there exists a value $t \in \mathbb{N}$ and a weight function $ : V \rightarrow \mathbb{N}$ such that the total weight of a subset $D\subseteq V$ is equal to $t$ if and only if $D$ is a minimal dominating set.
Schaudt, Oliver, Senger, Fabian
openaire +2 more sources