solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看13395次
Finding Independent Transversals Efficiently. (arXiv:1811.02687v1 [math.CO])
来源于:arXiv
We give an efficient algorithm that, given a graph $G$ and a partition
$V_1,\ldots,V_m$ of its vertex set, finds either an independent transversal (an
independent set $\{v_1,\ldots,v_m\}$ in $G$ such that $v_i\in V_i$ for each
$i$), or a subset $\mathcal B$ of vertex classes such that the subgraph of $G$
induced by $\bigcup\mathcal B$ has a small dominating set. A non-algorithmic
proof of this result has been known for a number of years and has been applied
to solve many other problems. Thus we are able to give algorithmic versions of
many of these applications, a few of which we describe explicitly here. 查看全文>>