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.05103OpenAlexW2181288515MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (5)
Contraction Blockers for Graphs with Forbidden Induced Paths ⋮ The most vital nodes with respect to independent set and vertex cover ⋮ Complexity of determining the most vital elements for the \(p\)-median and \(p\)-center location problems ⋮ Blockers for the stability number and the chromatic number ⋮ Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
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
This page was built for publication: Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures
