Sammanfattning I detta papper studerar vi kollektiva additiva trädspännen för speciella familjer av grafer inklusive plana grafer, grafer med avgränsat släkte, grafer med avgränsad trädbredd, grafer med avgränsad clique-bredd, och grafer med avgränsade ackordalitet. Vi säger att en graf G = (V, E) medger ett system av μ kollektiv additiv träd r-spanners om det finns ett system T (G) av som mest μ spännande träd av G sådan att för varje två hörn x, y av G en spännvidd träd Vi beskriver en allmän metod för att bygga en "liten" system av kollektiva additiv träd r-spanners med små värden av r för "väl" dekomponerbara grafer, och som en biprodukt visar (bland andra resultat) att varje viktad planar graf medger ett system av O ( ε n) kollektiv additiv träd 0-spanners, någon viktad graf med trädbredd som mest k − 1 medger ett system av k log 2 n kollektiv additiv träd 0-spanners, någon viktad graf med klique-width på de flesta k log 3/2 n kollektivt additiv träd (2w) - spanners, och någon viktad graf med storlek av största inducerade cykel vid de flesta c tillåter ett system av log 2 n kollektivt additiv träd (2-n) (w/2 kant) Det senare resultatet förfinas för viktade svagt ackorddiagram: varje sådan graf medger ett system av 4 log 2 n kollektiva additiv träd (2w)-spanners. Dessutom, baserat på denna samling av träd, vi härleda en kompakt och effektiv routing system för dessa familjer av grafer. Resultaten av detta dokument presenterades delvis vid ISAAC'05-konferensen [14].
För familjer av diagram med undantag av en fast mindre (inklusive planara och avgränsade släkten grafer), finns det en exakt RLS med etiketter av storlek O ( ε n log 2 n/ log log n) REF.
Collective Tree Spanners in Graphs with Bounded Parameters
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}