Максимальное взвешенное независимое множество прямоугольников

Authors

  • Э. Пилипосян Российско-Армянский (Славянский) университет

Abstract

На плоскости рассматривается множество прямоугольников M, стороны которых параллельны координатным осям. Считается, что все они расположены внутри некоторой большой прямоугольной рамки M и точно одной стороной опираются на какую-то ее сторону. Дополнительно предполагается, что все они имеют некоторый положительный вес. Предложенный в работе полиномиальный алгоритм в графе пересечений таких прямоугольников строит независимое множество максимального веса.

References

Гэри М., Джонсон Д., Вычислительные машины и труднорешаемые задачи, Мир, М., (1982).

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

J. Kratochvi, J. Nesetril. IND E P E ND E NT SE T and CL IQUE problems in intersectionde ¯ned classes of graphs, Commentationes Mathematicae Universitatis Carolinae, Vol. 31, No.1, 85–93, (1990).

P. Chalermsook and J. Chuzhoy. M aximum independent set of rectangles, In 20th annual ACM-SIAM SODA, 892–901, (2009).

P. K. Agarwal, M. J. van Kreveld, and S. Suri. L abel placement by maximum independent set in rectangles, Comput. Geom., 11(3–4), 209–218, (1998).

Downloads

Published

2021-12-10

How to Cite

Пилипосян, Э. (2021). Максимальное взвешенное независимое множество прямоугольников. Mathematical Problems of Computer Science, 38, 30–31. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/476

Issue

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

Section

Conference papers

License

Creative Commons License

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