The complexity of blocking (semi)total dominating sets with edge contractions

DOI10.1016/j.tcs.2022.12.028OpenAlexW4316035705MaRDI QIDQ2690876

Esther Galby

Publication date: 17 March 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2205.12821

zbMATH Keywords

total domination numberedge contraction\(H\)-free graphssemitotal domination numberblocker problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum edge blocker dominating set problem
• The most vital nodes with respect to independent set and vertex cover
• Blockers for the stability number and the chromatic number
• Matching interdiction
• Blockers for simple Hamiltonian paths in convex geometric graphs of even order
• Nonempty intersection of longest paths in series-parallel graphs
• Network flow interdiction on planar graphs
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• Exact algorithms for the minimum cost vertex blocker clique problem
• Critical vertices and edges in \(H\)-free graphs
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• Blocking total dominating sets via edge contractions
• Reducing the domination number of graphs via edge contractions and vertex deletions
• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
• Contraction Blockers for Graphs with Forbidden Induced Paths
• Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions
• Minimum vertex blocker clique problem
• Transversals of Longest Paths and Cycles
• The complexity of satisfiability problems
• Hard tiling problems with simple tiles

This page was built for publication: The complexity of blocking (semi)total dominating sets with edge contractions