The complexity of the reliable connectivity problem

DOI10.1007/3-540-54345-7_69MaRDI QIDQ4035248zbMATH OpenFDO

Authors Dimitris Kavadias, L. M. Kirousis, P. G. Spirakis

Publication date 18 May 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-54345-7_69

zbMATH Keywords

directed and acyclic graphsdirected pathNP-completeP-completeparallel complexityreliable connectivity problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The complexity of the reliable connectivity problem
• A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem
• The Complexity of the Residual Node Connectedness Reliability Problem
• The Complexity of Reliability Computations in Planar and Acyclic Graphs
• scientific article; zbMATH DE number 4097115

Cited in

(5)

• The complexity of the reliable connectivity problem
• The Complexity of the Residual Node Connectedness Reliability Problem
• The Complexity of Reliability Computations in Planar and Acyclic Graphs
• A simple variant of node connectivity is NP-complete
• scientific article; zbMATH DE number 1501630 (Why is no real title available?)

This page was built for publication: The complexity of the reliable connectivity problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4035248)