solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看16204次
A Short Note on Parameterized Computation of Network Reliability with respect to Treewidth. (arXiv:1712.09692v1 [math.CO])
来源于:arXiv
We consider the classic problem of network reliability. A network is given
together with a source vertex, one or more target vertices and probabilities
assigned to each of the edges. Each edge appears in the network with its
associated probability and the problem is to determine the probability of
having at least one source-to-target path. This problem is known to be NP-hard
for general networks and has been solved for several special families.
In this work we present a fixed-parameter algorithm based on treewidth, which
is a measure of tree-likeness of graphs. The problem was already known to be
solvable in linear time for bounded treewidth, however the known methods used
complicated structures and were not easy to implement. We provide a
significantly simpler and more intuitive algorithm that while remaining linear,
is much easier to implement. 查看全文>>