Ett träd t-spanner T i en graf G är ett spännträd där avståndet mellan varje par hörn är som mest t gånger deras avstånd i G. Detta begrepp motiveras av tillämpningar i kommunikationsnät, distribuerade system och nätverksdesign. Detta papper studerar grafteoretiska, algoritmiska och komplexa frågor om trädspännen. Det visas att ett träd 1-spanner, om det finns, i en viktad graf med m kanter och n hörn är en minsta spännvidd träd och kan hittas i O(m log β(m, n) tid, där β(m, n) = min{i på log (i) n ≤ m/n}. För varje fast t > 1 är däremot problemet med att bestämma förekomsten av ett träd t-spanner i en viktad graf visat sig vara NP-komplett. För oviktade grafer visas att det tar linjär tid att bygga ett träd 2-spanner, medan fastställandet av förekomsten av ett träd t-spanner är NP-komplett för varje fast t ≥ 4. Ett teorem som fångar strukturen av träd 2-spanners presenteras för oviktade grafer. För digrafer ges en O((m + n)α(m, n)-algoritm för att hitta ett träd t-spanner med t så liten som möjligt, där α(m, n) är en funktionell invers för Ackermans funktion. Resultaten för trädspännen på oriktade grafer utsträcks till "quasitree skiftnycklar" på digrafer. Dessutom härleds linjära tidsalgoritmer för verifiering av skiftnycklar för träd och kvasiträd.
Dessutom är det motsvarande beslutsproblemet att fastställa huruvida G medger en trädspännare med stretch σ NP-komplett för varje fast σ ≥ 4 (för σ = 2 är det polynom-tid solvable REF, medan för σ = 3 problemet är öppet).
Tree spanners
{'venue': 'SIAM J. Discrete Math', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}