Portal de Periódicos da CAPES

Maximizing Expectation on Vertex-Disjoint Cycle Packing

2014; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-319-09129-7_3

1611-3349

João Pedro Pedroso,

Optimization and Search Problems

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.