solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看80次
Approximating the number of maximal near perfect matchings in dense graphs. (arXiv:1807.04803v1 [math.CO])
来源于:arXiv
The main results of this paper provide a polynomial time algorithm for
approximating the logarithm of the number of maximal near perfect matchings in
dense graphs. By dense we mean that $|E(G)|\geq\alpha|V(G)|^2$ for some fixed
$\alpha>0$, and a maximal $\varepsilon$-near perfect matching is a maximal
matching which covers at least $(1-\varepsilon)|V(G)|$ vertices. More
precisely, we provide a deterministic algorithm that for a given (dense) graph
$G$ of order $n$ and a real number $\varepsilon>0$, returns either a conclusion
that $G$ has no $\varepsilon$-near perfect matching, or a positive real number
$m\leq1/2$, such that the logarithm of the number of maximal $\varepsilon$-near
perfect matchings in $G$ is at least $mn\log n$. The upper bound of such graphs
is always $1/2(n\log n)$. The running time of this algorithm is
$O(f(\varepsilon)n^{5/2})$, where $f(\cdot)$ is an explicit function.
Additionally, for a special class of dense graphs, we show that
$(1+\varepsilon)mn\log n$ 查看全文>>