Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!know!zaphod.mps.ohio-state.edu!samsung!uunet!mcsun!inria!geocub!mosbah
From: mosbah@geocub.greco-prog.fr ( )
Newsgroups: comp.theory
Subject: Network reliability?
Message-ID: <243@geocub.greco-prog.fr>
Date: 14 Sep 90 08:54:13 GMT
Organization: University of Bordeaux I - FRANCE
Lines: 15


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