mosbah@geocub.greco-prog.fr ( ) (09/14/90)
Is there anything known about the Network reliability problem [ND20]? (Given a graph G = (V,E), a subset V' of V, a rational failure probability p(e) for each edge e in E, a positive rational number q <= 1. Question: Is the probabilty q or greater that each pair of vertices in V' is joined by at least one path containing no failed edge? ) This problem problem is not known to be in NP in [G&J]. Is there any recent result? Thanks in advance. E-mail: mosbah@geocub.greco-prog.fr