scientific article; zbMATH DE number 176146

MaRDI QIDQ4035248zbMATH OpenFDO

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

Publication date 18 May 1993

zbMATH Keywords

NP-completedirected pathparallel complexityP-completedirected and acyclic graphsreliable 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

(4)

• The Complexity of Reliability Computations in Planar and Acyclic Graphs
• A simple variant of node connectivity is NP-complete
• The Complexity of the Residual Node Connectedness Reliability Problem
• The complexity of the reliable connectivity problem

This page was built for publication:

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