TY - JOUR

T1 - Dominant graphs for rectilinear network design with barriers

AU - Chhajed, Dilip

AU - Palekar, Udatta S.

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0031121624&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031121624&partnerID=8YFLogxK

U2 - 10.1080/07408179708966332

DO - 10.1080/07408179708966332

M3 - Article

AN - SCOPUS:0031121624

VL - 29

SP - 255

EP - 263

JO - IIE Transactions (Institute of Industrial Engineers)

JF - IIE Transactions (Institute of Industrial Engineers)

SN - 2472-5854

IS - 4

ER -