Zobrazeno 1 - 10
of 37
pro vyhledávání: '"05C85, 05C75"'
We investigate a relaxation of the notion of fractional treewidth-fragility, namely fractional tree-independence-number-fragility. In particular, we obtain polynomial-time approximation schemes for meta-problems such as finding a maximum-weight spars
Externí odkaz:
http://arxiv.org/abs/2402.18352
Autor:
Milanič, Martin, Uno, Yushi
A clique transversal in a graph is a set of vertices intersecting all maximal cliques. The problem of determining the minimum size of a clique transversal has received considerable attention in the literature. In this paper, we initiate the study of
Externí odkaz:
http://arxiv.org/abs/2309.14103
The branchwidth of a graph has been introduced by Roberson and Seymour as a measure of the tree-decomposability of a graph, alternative to treewidth. Branchwidth is polynomially computable on planar graphs by the celebrated ``Ratcatcher''-algorithm o
Externí odkaz:
http://arxiv.org/abs/2304.04517
We investigate a structural generalisation of treewidth we call $\mathcal{A}$-blind-treewidth where $\mathcal{A}$ denotes an annotated graph class. This width parameter is defined by evaluating only the size of those bags $B$ of tree-decompositions f
Externí odkaz:
http://arxiv.org/abs/2304.04504
Autor:
Bonnet, Édouard, Chakraborty, Dibyayan, Kim, Eun Jung, Köhler, Noleen, Lopes, Raul, Thomassé, Stéphan
We introduce the notion of delineation. A graph class $\mathcal C$ is said delineated if for every hereditary closure $\mathcal D$ of a subclass of $\mathcal C$, it holds that $\mathcal D$ has bounded twin-width if and only if $\mathcal D$ is monadic
Externí odkaz:
http://arxiv.org/abs/2204.00722
Autor:
Bachtler, Oliver, Heinrich, Irene
We present an interactive framework that, given a membership test for a graph class $\mathcal{G}$ and a number $k$, finds and tests unavoidable sets for the class of graphs in $\mathcal{G}$ of path-width at most $k$. We put special emphasis on the ca
Externí odkaz:
http://arxiv.org/abs/2010.08373
If a biconnected graph stays connected after the removal of an arbitrary vertex and an arbitrary edge, then it is called 2.5-connected. We prove that every biconnected graph has a canonical decomposition into 2.5-connected components. These component
Externí odkaz:
http://arxiv.org/abs/2003.01498
Autor:
Jovičić, Vladan
In the final project paper we consider a graph parameter called readability. Motivation for readability comes from bioinformatics applications. Graphs arising in problems related to genome sequencing are of small readability, which motivates the stud
Externí odkaz:
http://arxiv.org/abs/1612.07113
The notion of augmenting graphs generalizes Berge's idea of augmenting chains, which was used by Edmonds in his celebrated solution of the maximum matching problem. This problem is a special case of the more general maximum independent set (MIS) prob
Externí odkaz:
http://arxiv.org/abs/1410.8774
Autor:
LaMar, M. Drew
The Havel-Hakimi algorithm for constructing realizations of degree sequences for undirected graphs has been used extensively in the literature. A result by Kleitman and Wang extends the Havel-Hakimi algorithm to degree sequences for directed graphs.
Externí odkaz:
http://arxiv.org/abs/0906.0343