scientific article; zbMATH DE number 176146

zbMATH Open0768.68152MaRDI QIDQ4035248FDOQ4035248

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

Publication date: 18 May 1993

Title of this publication is not available (Why is that?)

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

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)

Cited In (4)

• 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
• The Complexity of Reliability Computations in Planar and Acyclic Graphs

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)