Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures

DOI10.1007/978-3-642-19222-7_17zbMath1326.05103MaRDI QIDQ3000504

Zsolt Tuza, Cristina Bazgan, Sonia Toubaline

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

Mathematics Subject Classification ID

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