solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看116次
Uniform generation of spanning regular subgraphs of a dense graph. (arXiv:1807.00964v1 [math.CO])
来源于:arXiv
Let $H_n$ be a graph on $n$ vertices and let $\overline{H_n}$ denote the
complement of $H_n$. Suppose that $\Delta = \Delta(n)$ is the maximum degree of
$\overline{H_n}$. We analyse three algorithms for sampling $d$-regular
subgraphs ($d$-factors) of $H_n$. This is equivalent to uniformly sampling
$d$-regular graphs which avoid a set $E(\overline{H_n})$ of forbidden edges.
Here $d=d(n)$ is a positive integer which may depend on $n$.
Two of these algorithms produce a uniformly random $d$-factor of $H_n$ in
expected runtime which is linear in $n$ and low-degree polynomial in $d$ and
$\Delta$. The first algorithm applies when $(d+\Delta)d\Delta = o(n)$. This
improves on an earlier algorithm by the first author, which required constant
$d$ and at most a linear number of edges in $\overline{H_n}$. The second
algorithm applies when $H_n$ is regular and $d^2+\Delta^2 = o(n)$, adapting an
approach developed by the first author together with Wormald. The third
algorithm is a simplification of t 查看全文>>