Klucz do drzew

Drzewo którym k -spanner (lub po prostu k -spanner ) wykresu to rozpinające poddrzewo z $w$${\ displaystyle T}$ odległość między każdą parą wierzchołków wynosi co najwyżej T $\ displaystyle T}$${\ displaystyle k}$ razy ich odległość w ${\ displaystyle G}$ .

Znane wyniki

Na temat kluczy do drzew napisano kilka artykułów. Jeden z nich nosił tytuł Tree Spanners , napisany przez matematyków Leizhen Cai i Dereka Corneila , który badał teoretyczne i algorytmiczne problemy związane z kluczami do drzew. Niektóre wnioski z tego artykułu są wymienione poniżej. ${\ displaystyle n}$$to zawsze$ wierzchołków wykresu, a to liczba jego krawędzi.

1. Drzewo 1-kluczowe, jeśli istnieje, jest minimalnym drzewem rozpinającym i można je znaleźć w ${\ Displaystyle {\ mathcal {O}} (m \ log \ beta (m ,n))}$ czas (pod względem złożoności) dla wykresu ważonego, gdzie ${\ Displaystyle \ beta (m, n) = \ min \ lewo \ {i \ mid \ log ^ {i} n \ równoważnik m / n \ prawo \}}$ . Co więcej, każdy dopuszczalny graf ważony drzewa o 1 kluczu zawiera unikalne minimalne drzewo rozpinające.
2. Drzewo o 2 kluczach można skonstruować w czasie, a problem z drzewem jest $}$ - zupełny dla ${\ Displaystyle {\ mathcal {O}} (m + n)$ dowolna stała liczba całkowita ${\ displaystyle t> 3}$ .
3. Złożoność znalezienia minimalnego klucza do drzewa w digrafie jest ${\ Displaystyle {\ mathcal {O}} ((m + n) \ cdot \ alpha ( ( m + n, n)}}$ , gdzie jest funkcjonalną odwrotnością funkcji Ackermanna ${\ Displaystyle \ alpha (m + n, n)}$
4. Minimalny 1 klucz ważonego wykresu można znaleźć w ${\ Displaystyle {\ mathcal {O}} (mn + n ^ {2} \ log (n)) }$ czas.
5. Dla dowolnej ustalonej liczby wymiernej $liczbami$ , czy wykres ważony zawiera drzewo t-spanner, jest NP-zupełne, nawet jeśli wszystkie wagi krawędzi są dodatnimi
6. Klucz do drzewa (lub minimalny klucz do drzewa) dwuznaku można znaleźć w czasie liniowym.
7. Dwuznak zawiera co najwyżej jeden klucz do drzewa.
8. $_$ można _

Zobacz też

• Klucz do wykresów
• Klucz geometryczny

•   Handke, Dagmar; Kortsarz, Guy (2000), „Klucze do drzew dla podwykresów i powiązanych problemów z pokryciem drzew”, Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000 Konstanz, Niemcy, 15–17 czerwca 2000, Proceedings , Lecture Notes in Computer Nauka, tom. 1928, s. 206–217, doi : 10.1007/3-540-40064-8_20 , ISBN 978-3-540-41183-3 .