TY - JOUR
AU - Piliposyan, Eduard T.
PY - 2021/12/10
Y2 - 2024/05/21
TI - A Note on Maximum Weight Independent Set in Outer-rectangle Graph
JF - Mathematical Problems of Computer Science
JA - MPCS
VL - 36
IS -
SE - Articles
DO -
UR - http://mpcs.sci.am/index.php/mpcs/article/view/265
SP - 51-56
AB - <p>An outer-rectangle graph is the intersection graph of rectangles lying inside a rectangular box and having exactly one edge on the boundary of the box. We present a polynomial-time algorithm for the problem of computing a maximum weight independent set in 2-side outer-rectangle graphs where any two rectangles lying on same edge of box do not intersect.</p>
ER -