The 0-1 inverse maximum stable set problem

DOI10.1016/J.DAM.2008.03.015zbMath1152.68039OpenAlexW2160736482MaRDI QIDQ955316

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

zbMATH Keywords

perfect graphsNP-hardnessinverse combinatorial optimizationapproximation ratiomaximum stable set problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Abstract computational complexity for mathematical programming problems (90C60) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (8)

The 0–1 inverse maximum independent set problem on forests and unicyclic graphs ⋮ Inverse chromatic number problems in interval and permutation graphs ⋮ Matching interdiction ⋮ Some Inverse Traveling Salesman Problems ⋮ On inverse traveling salesman problems ⋮ Notes on inverse bin-packing problems ⋮ Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs ⋮ Blockers and transversals

Cites Work

• On the hardness of approximating minimum vertex cover
• The maximum k-colorable subgraph problem for chordal graphs
• On chain and antichain families of a partially ordered set
• Optimization, approximation, and complexity classes
• Some partitions associated with a partially ordered set
• Towards optimal lower bounds for clique and chromatic number.
• Algorithmic graph theory and perfect graphs
• Inverse combinatorial optimization: a survey on problems, methods, and results
• On Approximate Solutions for Combinatorial Optimization Problems
• Inverse Optimization
• Graph Classes: A Survey
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Automata, Languages and Programming
• The structure of Sperner k-families
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The 0-1 inverse maximum stable set problem