The most vital nodes with respect to independent set and vertex cover
type: Item
instance of: scholarly article
title: The most vital nodes with respect to independent set and vertex cover
zbMATH Open document ID: 1236.05141
author: Cristina Bazgan
author: Sonia Toubaline
author: Zsolt Tuza
published in: Discrete Applied Mathematics
publication date: 2012-04-30T00:00:00Z
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 6029129
zbMATH Keywords: most vital vertices
zbMATH Keywords: independent set
zbMATH Keywords: vertex cover
zbMATH Keywords: time complexity
zbMATH Keywords: NP-hard
zbMATH Keywords: bipartite graph
zbMATH Keywords: bounded treewidth
zbMATH Keywords: cograph
MaRDI profile type: Publication
full work available at URL: j.dam.2011.06.023
OpenAlex ID: W2037935057
cites work: Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures
cites work: Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems
cites work: Approximation of satisfactory bisection problems
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: A Linear Recognition Algorithm for Cographs
cites work: Minimum \(d\)-blockers and \(d\)-transversals in graphs
cites work: Upper bounds to the clique width of graphs
cites work: Q4875228
cites work: A simple linear time algorithm for cograph recognition
cites work: Approximation Schemes for the Restricted Shortest Path Problem
cites work: Q4142699
cites work: On short paths interdiction problems: Total and node-wise limited interdiction
cites work: Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
cites work: Treewidth. Computations and approximations
cites work: The hardness of approximation: Gap location
cites work: Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
cites work: \(k\)-NLC graphs and polynomial algorithms
cites work: Deterministic network interdiction
cites work: Matching interdiction
cites work: Blockers and transversals
DOI: 10.1016/J.DAM.2011.06.023
description: scientific article; zbMATH DE number 6029129