A Note on Maximum Weight Independent Set in Outer-rectangle Graph

Authors

  • Eduard T. Piliposyan Russian-Armenian University

Keywords:

Weighted independent set, rectangle graphs, dynamic programming

Abstract

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.

References

P. Chalermsook and J. Chuzhoy. “Maximum independent set of rectangles". In 20th annual ACM-SIAM SODA, pp. 892-901, 2009.

P.K. Agarwal, M.J. van Kreveld, and S. Suri. “Label placement by maximum independent set in rectangles". Comput. Geom., 11(3-4): pp. 209-218, 1998.

S. Doerschler and H. Freeman. “A rule-based system for dense-map name placement". Communications of the ACM, 35 (1), pp. 68-79, 1992.

R.J. Fowler, M.S. Paterson, and S.L. Tanimoto. “Optimal packing and covering in the plane are NP-complete". Inform. Process. Lett., 12 (3), pp. 133-137, 1981.

T. Asano. Difficulty of the maximum independent set problem on intersection graphs of geometric objects. In 6th ICTAG, 1991.

P. Berman, B. DasGupta, S. Muthukrishnan, and S. Ramaswami. “Efficient approximation algorithms for tiling and packing problems with rectangles". J. Algorithm, 41, 2001.

L. Lewin-Eytan, J. Naor, and A. Orda. “Admission control in networks with advance reservations". Algorithmica, 40 (4): pp. 293-304, 2004.

T.M. Chan and S.Har-Peled. “Approximation algorithms for maximum independent set of pseudodisks". In 25th annual ACM SOCG, pp. 333-340, 2009.

G.H. Chen, M.T. Kuo, and J.P. Sheu. “An optimal time algorithm for finding a maximum weight in dependent set in a tree". BIT, vol. 23, pp. 353-356, 1988.

G. Frahling, U. Faigle. A combinatorial algorithm for weighted stable sets in bipartite graphs. Discrete applied mathematics, 2006.

M. Pal and G.P. Bhattacharjee, A sequential algorithm for finding a maximum weight k-independent set on interval graphs, Intern. J. Computer Mathematics, vol. 60, pp. 205-214, 1996.

Downloads

Published

2021-12-10

How to Cite

Piliposyan, E. T. . (2021). A Note on Maximum Weight Independent Set in Outer-rectangle Graph. Mathematical Problems of Computer Science, 36, 51–56. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/265

Issue

Vol. 36 (2012): Mathematical Problems of Computer Science

Section

Articles

License

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.