The 0-1 inverse maximum stable set problem
DOI10.1016/J.DAM.2008.03.015zbMATH Open1152.68039OpenAlexW2160736482MaRDI QIDQ955316FDOQ955316
Authors: Yerim Chung, Marc Demange 
Publication date: 19 November 2008
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2008.03.015
Recommendations
- The \(0-1\) inverse maximum independent set problem on forests and unicyclic graphs
- Robust algorithms for the stable set problem
- An exact algorithm for the maximum stable set problem
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- Polynomially solvable cases for the maximum stable set problem
inverse combinatorial optimizationNP-hardnessapproximation ratioperfect graphsmaximum stable set problem
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- Graph Classes: A Survey
- Algorithmic graph theory and perfect graphs
- Inverse combinatorial optimization: a survey on problems, methods, and results
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the hardness of approximating minimum vertex cover
- Title not available (Why is that?)
- The maximum k-colorable subgraph problem for chordal graphs
- Inverse Optimization
- On chain and antichain families of a partially ordered set
- Some partitions associated with a partially ordered set
- The structure of Sperner k-families
- On Approximate Solutions for Combinatorial Optimization Problems
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Automata, Languages and Programming
- Towards optimal lower bounds for clique and chromatic number.
- Title not available (Why is that?)
Cited In (9)
- Blockers and transversals
- Applications of the Inverse Theta Number in Stable Set Problems
- The \(0-1\) inverse maximum independent set problem on forests and unicyclic graphs
- Inverse chromatic number problems in interval and permutation graphs
- Some Inverse Traveling Salesman Problems
- Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs
- Notes on inverse bin-packing problems
- Matching interdiction
- On inverse traveling salesman problems
This page was built for publication: The 0-1 inverse maximum stable set problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q955316)
