Robust maximum weighted independent-set problems on interval graphs

DOI10.1007/s11590-012-0563-8zbMath1315.90059MaRDI QIDQ2439511

Fabrice Talla Nobibon, Roel Leus

Publication date: 14 March 2014

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

Full work available at URL: https://lirias.kuleuven.be/handle/123456789/359216

zbMATH Keywords

computational complexity; dynamic programming; combinatorial problems; independent set; interval graphs

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C47: Minimax problems in mathematical programming

Related Items

Unnamed Item, Trust Your Data or Not—StQP Remains StQP: Community Detection via Robust Standard Quadratic Optimization, Complexity of the robust weighted independent set problems on interval graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Maximum weight independent set of circular-arc graph and its application
• Mutual exclusion scheduling with interval graphs or related classes: complexity and algorithms
• Selection of programme slots of television channels for giving advertisement: a graph theoretic approach
• Robust discrete optimization and its applications
• Robust discrete optimization and network flows
• Algorithmic graph theory and perfect graphs
• A sequential algorithm for finding a maximum weightK-independent set on interval graphs
• The Price of Robustness
• On the complexity of a class of combinatorial optimization problems with uncertainty
• Finding a maximal weighted independent set in wireless networks