A lower bound of the expected maximum number of edge-disjoint \(s\)--\(t\) paths on probabilistic graphs

DOI10.1016/0166-218X(94)00084-QzbMath0822.05040OpenAlexW2014620579MaRDI QIDQ1842649

Peng Cheng, Shigeru Masuyama

Publication date: 10 August 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(94)00084-q

zbMATH Keywords

lower boundNP-hardedge-disjoint pathsprobabilistic graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph theory (05C99)

Cites Work

• A linear-time algorithm for finding an ambitus
• Bridges and Hamiltonian circuits in planar graphs
• Computational Complexity of Network Reliability Analysis: An Overview
• Unnamed Item

This page was built for publication: A lower bound of the expected maximum number of edge-disjoint \(s\)--\(t\) paths on probabilistic graphs