Независимые множества в случайных графах пересечений: различия между версиями

Некоторые задачи, имеющие отношение к случайным графам пересечений, остаются нерешенными. Почти все предложенные до сих пор алгоритмы построения больших независимых множеств и нахождения гамильтоновых циклов в случайных графах пересечений являются жадными. Интересное и важное направление исследований заключается в нахождении более проработанных алгоритмов для этих задач, превосходящих эффективностью жадные. Кроме того, все эти алгоритмы были представлены и проанализированы в модели равномерных случайных графов пересечений. Очень мало известно о том, как эти же алгоритмы будут работать, получив на входе экземпляр общей или даже регулярной модели случайных графов пересечений.