Complexity of most vital nodes for independent set in graphs related to tree structures

DOI10.1007/978-3-642-19222-7_17zbMATH Open1326.05103OpenAlexW2181288515MaRDI QIDQ3000504FDOQ3000504

Cristina Bazgan, Zsolt Tuza, 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

Recommendations

• The most vital nodes with respect to independent set and vertex cover
• Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
• Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
• The Maximum Independent Set Problem in Planar Graphs
• Independent domination on tree convex bipartite graphs

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Optimization, approximation, and complexity classes
• The hardness of approximation: Gap location
• Approximation Schemes for the Restricted Shortest Path Problem
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Blockers and transversals
• Deterministic network interdiction
• Vertex packings: Structural properties and algorithms
• Treewidth. Computations and approximations
• A Linear Recognition Algorithm for Cographs
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• Title not available (Why is that?)
• On short paths interdiction problems: Total and node-wise limited interdiction
• A simple linear time algorithm for cograph recognition
• Finding the \(k\) most vital edges with respect to minimum spanning tree

Cited In (5)

• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
• Contraction Blockers for Graphs with Forbidden Induced Paths
• Complexity of determining the most vital elements for the \(p\)-median and \(p\)-center location problems
• The most vital nodes with respect to independent set and vertex cover
• Blockers for the stability number and the chromatic number

This page was built for publication: Complexity of most vital nodes for independent set in graphs related to tree structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3000504)