The most vital nodes with respect to independent set and vertex cover
From MaRDI portal
Publication:411833
DOI10.1016/j.dam.2011.06.023zbMath1236.05141OpenAlexW2037935057MaRDI QIDQ411833
Cristina Bazgan, Zsolt Tuza, Sonia Toubaline
Publication date: 30 April 2012
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2011.06.023
bipartite graphindependent setNP-hardtime complexityvertex coverbounded treewidthcographmost vital vertices
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Minimum cost edge blocker clique problem, Exact algorithms for the minimum cost vertex blocker clique problem, \(d\)-transversals of stable sets and vertex covers in weighted bipartite graphs, Minimum edge blocker dominating set problem, Integer Programming Formulations for Minimum Spanning Tree Interdiction, Reducing the chromatic number by vertex or edge deletions, Integer programming methods for solving binary interdiction games, Contraction Blockers for Graphs with Forbidden Induced Paths, Assistance and interdiction problems on interval graphs, Reducing the vertex cover number via edge contractions, Mixed integer bilevel optimization with a \(k\)-optimal follower: a hierarchy of bounds, On designing networks resilient to clique blockers, A survey on mixed-integer programming techniques in bilevel optimization, The complexity of blocking (semi)total dominating sets with edge contractions, Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives, Study of the Matching Interdiction Problem in Some Molecular Graphs of Dendrimers, Reducing the domination number of graphs via edge contractions and vertex deletions, Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions, Critical edges for the assignment problem: complexity and exact resolution, Interdiction Games and Monotonicity, with Application to Knapsack Problems, Detecting critical node structures on graphs: A mathematical programming approach, Critical vertices and edges in \(H\)-free graphs, The maximum clique interdiction problem, Blockers for the stability number and the chromatic number, A dynamic reformulation heuristic for generalized interdiction problems, Unnamed Item, Unnamed Item, Contraction and deletion blockers for perfect graphs and \(H\)-free graphs, Blocking total dominating sets via edge contractions, Reducing graph transversals via edge contractions, Complexity and algorithms for constant diameter augmentation problems, Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions, Multilevel Approaches for the Critical Node Problem, On the Independent Set Interdiction Problem, Using edge contractions to reduce the semitotal domination number
Cites Work
- Unnamed Item
- Unnamed Item
- Minimum \(d\)-blockers and \(d\)-transversals in graphs
- Matching interdiction
- On short paths interdiction problems: Total and node-wise limited interdiction
- Approximation of satisfactory bisection problems
- Blockers and transversals
- Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
- The hardness of approximation: Gap location
- \(k\)-NLC graphs and polynomial algorithms
- Treewidth. Computations and approximations
- A simple linear time algorithm for cograph recognition
- Deterministic network interdiction
- Upper bounds to the clique width of graphs
- Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures
- Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems
- A Linear Recognition Algorithm for Cographs
- Approximation Schemes for the Restricted Shortest Path Problem
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
