Results 41 to 50 of about 1,490 (139)
Clustered colouring of graph classes with bounded treedepth or pathwidth
Combinatorics, Probability and Computing, 2022 AbstractThe clustered chromatic number of a class of graphs is the minimum integer $k$ such that for some integer $c$ every graph in the class is $k$ -colourable with monochromatic components of size at most $c$ . We determine the clustered chromatic number of any minor-closed class with bounded treedepth, and prove a best possible upper bound on
Norin, S, Scott, A, Wood, DR
openaire +2 more sources
Subexponential parameterized algorithms for graphs of polynomial growth [PDF]
, 2016 We show that for a number of parameterized problems for which only $2^{O(k)} n^{O(1)}$ time algorithms are known on general graphs, subexponential parameterized algorithms with running time $2^{O(k^{1-\frac{1}{1+\delta}} \log^2 k)} n^{O(1)}$ are possible
Marx, Dániel, Pilipczuk, M
core +2 more sources
Exploring Subexponential Parameterized Complexity of Completion Problems [PDF]
, 2014 Let ${\cal F}$ be a family of graphs. In the ${\cal F}$-Completion problem, we are given a graph $G$ and an integer $k$ as input, and asked whether at most $k$ edges can be added to $G$ so that the resulting graph does not contain a graph from ${\cal F}$
Drange, Pål Grønås +3 more
core +3 more sources
Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms
, 2017 We present two new combinatorial tools for the design of parameterized algorithms. The first is a simple linear time randomized algorithm that given as input a $d$-degenerate graph $G$ and an integer $k$, outputs an independent set $Y$, such that for ...
Lokshtanov, Daniel +4 more
core +1 more source
Smaller Parameters for Vertex Cover Kernelization [PDF]
, 2017 We revisit the topic of polynomial kernels for Vertex Cover relative to structural parameters. Our starting point is a recent paper due to Fomin and Str{\o}mme [WG 2016] who gave a kernel with $\mathcal{O}(|X|^{12})$ vertices when $X$ is a vertex set ...
Hols, Eva-Maria C., Kratsch, Stefan
core +2 more sources
Classical and Bayesian Methodology for a New Inverse Statistical Model
Engineering Reports, Volume 7, Issue 8, August 2025.This article introduces a two‐parameter statistical model derived by applying an inverse transformation to the cumulative distribution function of the Pham distribution. The proposed model offers a flexible and tractable framework for modeling skewed and heavy‐tailed data, making it well‐suited for applications in reliability engineering, survival ...
Ibrahim Elbatal +5 more
wiley +1 more source
Local certification of MSO properties for bounded treedepth graphs
, 2021 The graph model checking problem consists in testing whether an input graph satisfies a given logical formula. In this paper, we study this problem in a distributed setting, namely local certification. The goal is to assign labels to the nodes of a network to certify that some given property is satisfied, in such a way that the labels can be checked ...
Bousquet, Nicolas +2 more
openaire +2 more sources
Bayesian Robust Data Envelopment Analysis With Heavy‐Tailed Priors
Journal of Mathematics, Volume 2025, Issue 1, 2025.Data envelopment analysis (DEA) remains one of the most widely used methods for evaluating the efficiency of decision‐making units (DMUs). However, it is highly sensitive to outliers, especially in cases involving imbalanced data. Classical Bayesian DEA models typically employ Beta distributions as priors, which are not effective in mitigating the ...
Mehmet Ali Cengiz +2 more
wiley +1 more source
Degree and Sensitivity: Tails of Two Distributions [PDF]
, 2016 The sensitivity of a Boolean function f is the maximum, over all inputs x, of the number of sensitive coordinates of x (namely the number of Hamming neighbors of x with different f-value).
Gopalan, Parikshit +2 more
core +1 more source
On tree decompositions whose trees are minors
Journal of Graph Theory, Volume 106, Issue 2, Page 296-306, June 2024.Abstract In 2019, Dvořák asked whether every connected graph G $G$ has a tree decomposition ( T , B ) $(T,{\rm{ {\mathcal B} }})$ so that T $T$ is a subgraph of G $G$ and the width of ( T , B ) $(T,{\rm{ {\mathcal B} }})$ is bounded by a function of the treewidth of G $G$.
Pablo Blanco +5 more
wiley +1 more source