The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes

DOI10.1137/050629276zbMath1165.68034OpenAlexW2030606633MaRDI QIDQ5454268

Janka Chlebíková, Miroslav Chlebík

Publication date: 28 March 2008

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/050629276

zbMATH Keywords

independent setgeometric intersection graphsrectangle graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (13)

Bounded clique cover of some sparse graphs ⋮ Finding a Maximum Clique in a Grounded 1-Bend String Graph ⋮ On independent set in \(B_1\)-EPG graphs ⋮ Complexity aspects of variants of independent Roman domination in graphs ⋮ Hardness and approximation for L-EPG and \(B_1\)-EPG graphs ⋮ Geometric Packing under Nonuniform Constraints ⋮ Combinatorial problems on \(H\)-graphs ⋮ On the kernel and related problems in interval digraphs ⋮ Independent roman $\{3\}$-domination ⋮ On \(H\)-topological intersection graphs ⋮ Domination in Geometric Intersection Graphs ⋮ On Covering Segments with Unit Intervals ⋮ The maximum clique problem in multiple interval graphs

This page was built for publication: The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes