The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
From MaRDI portal
Publication:5454268
DOI10.1137/050629276zbMath1165.68034MaRDI 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
90C35: Programming involving graphs or networks
68Q25: Analysis of algorithms and problem complexity
90C60: Abstract computational complexity for mathematical programming problems
90C27: Combinatorial optimization
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Geometric Packing under Nonuniform Constraints, Independent roman $\{3\}$-domination, Domination in Geometric Intersection Graphs, On \(H\)-topological intersection graphs, On Covering Segments with Unit Intervals, Finding a Maximum Clique in a Grounded 1-Bend String Graph, On the kernel and related problems in interval digraphs, Combinatorial problems on \(H\)-graphs, On independent set in \(B_1\)-EPG graphs, Hardness and approximation for L-EPG and \(B_1\)-EPG graphs, The maximum clique problem in multiple interval graphs, Bounded clique cover of some sparse graphs, Complexity aspects of variants of independent Roman domination in graphs