## Abstract

Given a set of points on a Cartesian plane and the coordinate axes, the rectilinear network design problem is to find a network, with arcs parallel to either one of the axes, that minimizes the fixed and the variable costs of interactions between a specified set of pairs of points. We show that, even in the presence of arbitrary barriers, an optimal solution to the problem (when feasible) is contained in a grid graph defined by the set of given points and the barriers. This converts the spatial problem to a combinatorial problem. Finally we show connections between the rectilinear network design problem and a number of well-known problems. Thus this paper unifies the known dominating set results for these problems and extends the results to the case with barriers.

Original language | English (US) |
---|---|

Pages (from-to) | 255-263 |

Number of pages | 9 |

Journal | IIE Transactions (Institute of Industrial Engineers) |

Volume | 29 |

Issue number | 4 |

DOIs | |

State | Published - 1997 |

## ASJC Scopus subject areas

- Industrial and Manufacturing Engineering