The hitting set is a fundamental concept in graph theory and combinatorial optimization. In this paper, we study a special class of the hitting set problem in grid graphs. Given an \(n\times m\) grid graph \(G=(V,E)\) , a rectangle eliminating set is an edge subset \(A\subseteq E\) such that \(G-A\) contains no rectangular outlines. The minimum cardinality of the rectangle eliminating set is the rectangle eliminating number, denoted by S(n, m). We derive several upper bounds for S(n, m) by periodic sampling, binary decomposition and hybrid constructions. In particular, for square grids, we show that \(S(n,n) \le \frac{2n^2}{3} + \frac{40}{3}\sqrt{2} \cdot \sqrt{n} + 3\) when \(n \ge 32\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Constructive Upper Bounds on the Rectangle Eliminating Number in Grid Graphs

  • Enguo Niu,
  • Zhongzheng Tang

摘要

The hitting set is a fundamental concept in graph theory and combinatorial optimization. In this paper, we study a special class of the hitting set problem in grid graphs. Given an \(n\times m\) grid graph \(G=(V,E)\) , a rectangle eliminating set is an edge subset \(A\subseteq E\) such that \(G-A\) contains no rectangular outlines. The minimum cardinality of the rectangle eliminating set is the rectangle eliminating number, denoted by S(n, m). We derive several upper bounds for S(n, m) by periodic sampling, binary decomposition and hybrid constructions. In particular, for square grids, we show that \(S(n,n) \le \frac{2n^2}{3} + \frac{40}{3}\sqrt{2} \cdot \sqrt{n} + 3\) when \(n \ge 32\) .