Given two point sets P and R lying in the first quadrant \(Q_1\) and such that \((0,0) \in R\) , the Rectilinear Steiner Forest Arborescence (RSFA) problem is to find the minimum-length spanning forest F such that for each point \(p \in P\) , there exists a root \(r \in R\) , with \(\mathrm x(r) \le \textrm{x}(p)\) and \(\textrm{y}(r) \le \textrm{y}(p)\) , and a path in F connecting p to r whose length is equal to \((\textrm{x}(p)-\textrm{x}(r))+(\textrm{y}(p)-\textrm{y}(r))\) . The RSFA problem is a natural generalization of the Rectilinear Steiner Arborescence (RSA) problem, where \(R=\{(0,0)\}\) , and thus it is NP-hard. Herein, we briefly discuss a polynomial time approximation scheme for the RSFA problem, present a fast 2-approximation algorithm and provide a fixed-parameter algorithm.

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

The Rectilinear Steiner Forest Arborescence

  • Łukasz Mielewczyk,
  • Leonidas Palios,
  • Paweł Żyliński

摘要

Given two point sets P and R lying in the first quadrant \(Q_1\) and such that \((0,0) \in R\) , the Rectilinear Steiner Forest Arborescence (RSFA) problem is to find the minimum-length spanning forest F such that for each point \(p \in P\) , there exists a root \(r \in R\) , with \(\mathrm x(r) \le \textrm{x}(p)\) and \(\textrm{y}(r) \le \textrm{y}(p)\) , and a path in F connecting p to r whose length is equal to \((\textrm{x}(p)-\textrm{x}(r))+(\textrm{y}(p)-\textrm{y}(r))\) . The RSFA problem is a natural generalization of the Rectilinear Steiner Arborescence (RSA) problem, where \(R=\{(0,0)\}\) , and thus it is NP-hard. Herein, we briefly discuss a polynomial time approximation scheme for the RSFA problem, present a fast 2-approximation algorithm and provide a fixed-parameter algorithm.