Кіріспе
Граф теориясында, байланысқан үстемдік жиыны және максималды жапырақтарды қамтитын ағаш – бағытталмаған графта анықталатын екі тығыз байланысты құрылым.
Алгоритмдер
Берілген шектен кіші өлшемді байланысқан үстемдік жиынының бар-жоғын тексеру немесе, эквивалентті түрде, кем дегенде берілген саны бар жапырақтары бар аралықтағы ағаштың бар-жоғын тексеру NP-толық. Сондықтан, ең аз байланысқан үстемдік жиыны проблемасы мен ең көп жапыраққа созылатын ағаш проблемасын полиномиалдық уақытта шешу мүмкін емес деп есептеледі. Жақындастыру алгоритмдері тұрғысынан қарағанда, байланысқан үстемдік және максималды жапыраққа созылатын ағаштар бірдей емес: біреуін берілген жақындастыру қатынасымен жақындастыру, екіншісін сол қатынаспен жақындастырудан өзгеше. Ең аз байланысқан үстемдік жиыны үшін 2 ln Δ + O(1) коэффициентін қамтитын жақындастыру бар, мұнда Δ – G графигіндегі төбелердің ең жоғары дәрежесі. Максималды жапыраққа созылатын ағаш проблемасы MAX SNP-қатты, яғни полиномиалдық уақытты жақындастыру схемасының болуы күмәнді. Алайда, оны полиномиалдық уақытта 2 еселік жақындастыру арқылы шешуге болады. Екі проблема да n төбелі графтарда O(1.9^n) уақытында шешіледі. Максималды жапырақ проблемасы параметрге қатысты шешіледі, яғни оны жапырақтар санына қатысты экспоненциалды уақытта, бірақ кіріс графигінің өлшеміне қатысты полиномиалдық уақытта шешуге болады. Бұл алгоритмдердің клам мәні (интуитивті түрде, мәселені ақылға қонымды уақытта шешуге болатын жапырақтар саны) алгоритмдердің жақсаруымен шамамен 37-ге дейін бірте-бірте өсті және кем дегенде 50-ге қол жеткізуге болады деп ұсынылған. Ең жоғары дәрежесі үшке тең графтарда байланысқан үстемдік жиыны және оның толықтырылған максималды жапыраққа созылатын ағаш проблемасын сызықтық матроидтар үшін матроидтық паритет проблемасының мысалына түрлендіру арқылы полиномиалдық уақытта шешуге болады.
The maximum leaf spanning tree problem is MAX SNP hard, implying that no polynomial time approximation scheme is likely. However, it can be approximated to within a factor of 2 in polynomial time. Both problems may be solved, on n vertex graphs, in time O(1.9^(n)). The maximum leaf problem is fixed parameter tractable, meaning that it can be solved in time exponential in the number of leaves but only polynomial in the input graph size. The klam value of these algorithms (intuitively, a number of leaves up to which the problem can be solved within a reasonable amount of time) has gradually increased, as algorithms for the problem have improved, to approximately 37, and it has been suggested that at least 50 should be achievable. In graphs of maximum degree three, the connected dominating set and its complementary maximum leaf spanning tree problem can be solved in polynomial time, by transforming them into an instance of the matroid parity problem for linear matroids.
Қолданбалар
Қосылған доминантты жиынтар мобильді желілерде маршрутты есептеуде пайдалы. Бұл қолданбада кішігірім қосылған доминантты жиын байланыс үшін негіз ретінде қолданылады, ал осы жиынға кірмейтін түйіндер жиынға кіретін көршілері арқылы хабар алмасып қарым-қатынас жасайды. Максималды жапырақ саны шектелген параметрлі алгоритмдерді жасауда қолданылды: бірнеше NP-қиын оптимизациялық мәселелер шектелген максималды жапырақ саны бар графтар үшін полиномиалдық уақытта шешіледі.