Complexity and Applications of Edge-Induced Vertex-Cuts
classification
💻 cs.DM
cs.CC
keywords
vertex-cutsedge-inducedapplicationscomplexitynotionalgorithmscomparecomputing
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.