Trädnyckel - Tree spanner

Ett träd k -spanner (eller helt enkelt k -spanner ) av en kurva är en som spänner över underträd av i vilken avståndet mellan varje par av hörn är vid de flesta gånger deras avstånd i . ${\ displaystyle G}$ ${\ displaystyle T}$${\ displaystyle G}$${\ displaystyle k}$${\ displaystyle G}$

Kända resultat

Det finns flera papper skrivna om trädskruvarna. En av dessa kallades Tree Spanners skriven av matematikerna Leizhen Cai och Derek Corneil , som utforskade teoretiska och algoritmiska problem förknippade med trädnycklar. Några av slutsatserna från det uppsatsen listas nedan. är alltid antalet vertiklar i diagrammet och är antalet kanter. ${\ displaystyle n}$${\ displaystyle m}$

1. Ett träd 1-skiftnyckel, om det finns, är ett minimum sträckande träd och kan hittas i tid (i termer av komplexitet) för ett viktat diagram, där .${\ displaystyle {\ mathcal {O}} (m \ log \ beta (m, n))}$${\ displaystyle \ beta (m, n) = \ min \ vänster \ {i \ mid \ log ^ {i} n \ leq m / n \ höger \}}$
2. Ett träd 2-skiftnyckel kan konstrueras i linjär tid, och trädspännarproblemet är NP-komplett för alla fasta heltal .${\ displaystyle t}$${\ displaystyle t> 3}$
3. Komplexiteten för att hitta en minsta trädskruv i en digraph är , var är en funktionell invers av Ackermann-funktionen${\ displaystyle {\ mathcal {O}} ((m + n) \ cdot \ alpha (m + n, n))}$${\ displaystyle \ alpha (m + n, n)}$
4. Minsta 1-skiftnyckel för en vägd graf kan hittas i tid.${\ displaystyle {\ mathcal {O}} (mn + n ^ {2} \ log (n))}$
5. För alla fasta rationella nummer är det NP-komplett för att bestämma om en vägd graf innehåller en träd-t-nyckel, även om alla kantvikter är positiva heltal.${\ displaystyle t> 1}$
6. En trädnyckel (eller en minsta trädnyckel) av en digraph kan hittas i linjär tid.
7. En digraph innehåller högst en trädnyckel.
8. Den kvasitrömsnyckeln i en vägd digraf kan hittas i tid.${\ displaystyle {\ mathcal {O}} (m \ log \ beta (m, n))}$
9. Trädets 1-skiftnyckel i ett viktat diagram är ett minimum sträckande träd. Dessutom innehåller varje tillåtet viktad graf för varje 1-nyckel ett unikt minimum sträckande träd.${\ displaystyle G}$
10. En träd 2-nyckel (om den finns) i en graf kan hittas i tid.${\ displaystyle {\ mathcal {O}} (m + n)}$

Se även

• Grafnyckel
• Geometrisk nyckel

referenser

• Handke, Dagmar; Kortsarz, Guy (2000), "Trädskruvar för undergrafer och relaterade trädtäckande problem", Grafteoretiska begrepp inom datavetenskap: 26th International Workshop, WG 2000 Konstanz, Tyskland, 15–17 juni 2000, Proceedings , Lecture Notes in Computer Science, 1928 , s. 206–217, doi : 10.1007 / 3-540-40064-8_20 , ISBN  978-3-540-41183-3.