Results 51 to 60 of about 1,490 (139)
Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters [PDF]
, 2019 We continue and extend previous work on the parameterized complexity analysis of the NP-hard Stable Roommates with Ties and Incomplete Lists problem, thereby strengthening earlier results both on the side of parameterized hardness as well as on the side ...
Bredereck, Robert +3 more
core +1 more source
An Improved Time-Efficient Approximate Kernelization for Connected Treedepth Deletion Set
, 2022 We study the CONNECTED η-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 ηand G[S] is connected.
Eiben, Eduard +2 more
openaire +2 more sources
Model-checking for successor-invariant first-order formulas on graph classes of bounded expansion [PDF]
, 2017 A successor-invariant first-order formula is a formula that has access to an auxiliary successor relation on a structure's universe, but the model relation is independent of the particular interpretation of this relation.
Kreutzer, Stephan +5 more
core +3 more sources
Reconfiguration on sparse graphs [PDF]
, 2015 A vertex-subset graph problem Q defines which subsets of the vertices of an input graph are feasible solutions. A reconfiguration variant of a vertex-subset problem asks, given two feasible solutions S and T of size k, whether it is possible to transform
A Dawar +16 more
core +2 more sources
Specifying prior distributions in reliability applications
Applied Stochastic Models in Business and Industry, Volume 40, Issue 1, Page 5-62, January/February 2024.Especially when facing reliability data with limited information (e.g., a small number of failures), there are strong motivations for using Bayesian inference methods. These include the option to use information from physics‐of‐failure or previous experience with a failure mode in a particular material to specify an informative prior distribution ...
Qinglong Tian +3 more
wiley +1 more source
Treedepth and 2-treedepth in graphs with no long induced paths
Huynh, Joret, Micek, Seweryn, and Wollan (Combinatorica, 2022) introduced a graph parameter, later referred to as 2-treedepth and denoted $\mathrm{td}_2(\cdot)$. The parameter is the natural 2-connected version of treedepth. For every graph, 2-treedepth is at most the treedepth but can be much smaller: long paths have arbitrary treedepth but 2 ...
Hodor, Jędrzej +2 more
openaire +2 more sources
On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem [PDF]
, 2018 We study the parameterized complexity of the Bounded-Degree Vertex Deletion problem (BDD), where the aim is to find a maximum induced subgraph whose maximum degree is below a given degree bound.
Ganian, Robert +2 more
core +1 more source
Automated Problem Decomposition for the Boolean Domain with Genetic Programming [PDF]
, 2013 Researchers have been interested in exploring the regularities and modularity of the problem space in genetic programming (GP) with the aim of decomposing the original problem into several smaller subproblems.
A. Moraglio +6 more
core +2 more sources
Homomorphism Reconfiguration via Homotopy [PDF]
, 2014 We consider the following problem for a fixed graph H: given a graph G and two H-colorings of G, i.e. homomorphisms from G to H, can one be transformed into the other by changing one color at a time, maintaining an H-coloring throughout.This is the same ...
Wrochna, Marcin
core +2 more sources
About Treedepth and Related Notions
, 2017 Dissertation, RWTH Aachen University, 2017; Aachen 1 Online-Ressource (getrennte Zählung) : Illustrationen (2017).
openaire +2 more sources