Complexity and Applications of Edge-Induced Vertex-Cuts
arXiv:cs/0607109
Abstract
Motivated by hypergraph decomposition algorithms, we introduce the notion of edge-induced vertex-cuts and compare it with the well-known notions of edge-cuts and vertex-cuts. We investigate the complexity of computing minimum edge-induced vertex-cuts and demonstrate the usefulness of our notion by applications in network reliability and constraint satisfaction.
17 pages, 5 figures, 2 tables