On the equivalence in complexity among three computation problems on maximum number of edge-disjoint \(s\)-\(t\) paths in a probabilistic graph

DOI10.1016/0020-0190(94)00076-XzbMath0942.68580OpenAlexW2096206993MaRDI QIDQ1334642

Shigeru Masuyama, Peng Cheng

Publication date: 25 September 1994

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00076-x

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Stochastic network models in operations research (90B15) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Cites Work

• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Enumeration and Reliability Problems
• Unnamed Item
• Unnamed Item

This page was built for publication: On the equivalence in complexity among three computation problems on maximum number of edge-disjoint \(s\)-\(t\) paths in a probabilistic graph