A simple variant of node connectivity is NP-complete

DOI10.1080/00207168608803546zbMath0655.68040OpenAlexW2079580293MaRDI QIDQ3802606

K. V. S. Ramarao

Publication date: 1986

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207168608803546

zbMATH Keywords

distributed systemsfault-tolerancenetwork partitionsnode connectivity2NP- completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15) Theory of software (68N99)

Cites Work

• Unnamed Item
• The node-deletion problem for hereditary properties is NP-complete
• An Information-Based Model for Failure-Handling in Distributed Database Systems
• Node-Deletion NP-Complete Problems
• Finding the Vertex Connectivity of Graphs
• Edge-Deletion Problems
• An Algorithm for Determining Whether the Connectivity of a Graph is at Leastk
• Network Flow and Testing Graph Connectivity

This page was built for publication: A simple variant of node connectivity is NP-complete