Complexity and Applications of Edge-Induced Vertex-Cuts
<|reference_start|>Complexity and Applications of Edge-Induced Vertex-Cuts: 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.<|reference_end|>
@article{samer2006complexity,
    title={Complexity and Applications of Edge-Induced Vertex-Cuts},
    author={Marko Samer and Stefan Szeider},
    journal={arXiv preprint arXiv:cs/0607109},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0607109},
    primaryClass={cs.DM cs.CC}
}