2006/07/25 by Marko Samer, Stefan Szeider, Samer, Marko +1 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Artificial intelligence #Combinatorics #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computer science #Discrete Mathematics (cs.DM) #Edge contraction #Edge cover #Enhanced Data Rates for GSM Evolution #F.2.2 #FOS: Computer and information sciences #G.2.2 #Graph #Hypergraph #Interconnection Networks and Systems #Mathematics #Vertex (graph theory) #cs.CC #cs.DM
paper · pdf · doi:10.48550/arxiv.cs/0607109
published in arXiv (Cornell University) (Cornell University) · 17 pages, 5 figures, 2 tables
openalex publication_date 2006/07/25 · arxiv created 2006/07/31 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.