Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems

DOI10.1007/s12351-008-0020-8zbMath1154.90577OpenAlexW1980681426MaRDI QIDQ1001381

Frederico Della Croce, Vangelis Th. Paschos

Publication date: 17 February 2009

Published in: Operational Research. An International Journal (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12351-008-0020-8

zbMATH Keywords

set coveringworst-case complexitydominance conditionsMax cut

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Cites Work

• Pathwidth of cubic graphs and exact algorithms
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• A note on the complexity of minimum dominating set
• Improved worst-case complexity for the MIN 3-SET COVERING problem
• Vertex Cover: Further Observations and Further Improvements
• Automata, Languages and Programming
• Graph-Theoretic Concepts in Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems