Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures
From MaRDI portal
Publication:3000504
DOI10.1007/978-3-642-19222-7_17zbMath1326.05103MaRDI QIDQ3000504
Zsolt Tuza, Sonia Toubaline, Cristina Bazgan
Publication date: 19 May 2011
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-19222-7_17
68Q25: Analysis of algorithms and problem complexity
05C05: Trees
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
The most vital nodes with respect to independent set and vertex cover, Blockers for the stability number and the chromatic number, Complexity of determining the most vital elements for the \(p\)-median and \(p\)-center location problems, Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions, Contraction Blockers for Graphs with Forbidden Induced Paths
Cites Work
- Unnamed Item
- On short paths interdiction problems: Total and node-wise limited interdiction
- Blockers and transversals
- Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
- Optimization, approximation, and complexity classes
- The hardness of approximation: Gap location
- Treewidth. Computations and approximations
- A simple linear time algorithm for cograph recognition
- Deterministic network interdiction
- Finding the \(k\) most vital edges with respect to minimum spanning tree
- A Linear Recognition Algorithm for Cographs
- Approximation Schemes for the Restricted Shortest Path Problem
- Vertex packings: Structural properties and algorithms
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth