Maximizing Expectation on Vertex-Disjoint Cycle Packing
Maximizing Expectation on Vertex-Disjoint Cycle Packing
复制标题
最大化顶点不相交循环填充的期望
DOI：
10.1007/978-3-319-09129-7_3
复制
发表时间：
2014
影响因子：
8.8
通讯作者：
João Pedro Pedroso
中科院分区：
文献类型：
--
作者：
João Pedro Pedroso
本文提出了一种计算有向图中顶点和/或弧以已知概率失效的顶点不交圈的最大集的期望长度的方法。该方法有一个直接的实际应用：它可以用于解决肾脏交换计划在常见的情况下，基本的图形是不可靠的。报告和分析了实际基准测试实例的结果。
This paper proposes a method for computing the expectation for the length of a maximum set of vertex-disjoint cycles in a digraph where vertices and/or arcs are subject to failure with a known probability. This method has an immediate practical application: it can be used for the solution of a kidney exchange program in the common situation where the underlying graph is unreliable. Results for realistic benchmark instances are reported and analyzed.