Robust maximum weighted independent-set problems on interval graphs

DOI10.1007/s11590-012-0563-8zbMath1315.90059OpenAlexW1992051595MaRDI 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 complexitydynamic programmingcombinatorial problemsindependent setinterval graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Minimax problems in mathematical programming (90C47)

Related Items (3)

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

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

This page was built for publication: Robust maximum weighted independent-set problems on interval graphs