Complexity of the robust weighted independent set problems on interval graphs

DOI10.1007/s11590-014-0773-3zbMath1339.90332arXiv1405.5376WikidataQ59405802 ScholiaQ59405802MaRDI QIDQ2018858

Adam Kasperski, Paweł Zieliński

Publication date: 25 March 2015

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1405.5376

zbMATH Keywords

computational complexity; independent set; robust optimization; interval graph

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C47: Minimax problems in mathematical programming

90C60: Abstract computational complexity for mathematical programming problems

Related Items

Unnamed Item, Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty

Cites Work

• Unnamed Item
• General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems
• Selection of programme slots of television channels for giving advertisement: a graph theoretic approach
• Discrete optimization with interval data. Minmax regret and fuzzy approach
• An approximation algorithm for interval data minmax regret combinatorial optimization problems
• Robust discrete optimization and its applications
• Single machine scheduling with scenarios
• Robust maximum weighted independent-set problems on interval graphs
• A sequential algorithm for finding a maximum weightK-independent set on interval graphs