Med tanke på en graf G = (V, E), en delgraf G = (V, H), H  på E är en k-spanner av G om för något par hörn u, w  på V den uppfyller d H (u, w) ≤ k · d G (u, w). Det grundläggande k-spannerproblemet är att hitta en k-spanner av en given graf G med minsta möjliga antal kanter. I detta dokument behandlas approximationsalgoritmer för detta och vissa relaterade problem för k > 2, som är kända för att vara.(2 log 1−μ n )-ojämförbara. Det grundläggande k-spanner problemet över oriktade grafer med k > 2 har getts en sublinjär kvot approximation algoritm (med förhållandet ungefär O(n 2/(k+1) ), men inga sådana algoritmer var kända för andra varianter av problemet, inklusive riktade och klient-server varianter, samt för relaterade k-DSS problem. Vi presenterar de första approximationsalgoritmerna för dessa problem med sublinjär approximationsgrad. Det andra bidraget i detta papper är att karakterisera några breda familjer av grafer där problemen medger en logaritmisk och en polylogaritmisk approximation förhållande. Dessa familjer karakteriseras som innehållande grafer som har optimala eller "nära-optimala" skiftnycklar med vissa önskvärda egenskaper, såsom att vara ett träd, har låg arboricity eller har låg omkrets. Alla våra resultat generaliseras till de riktade och klient-server-varianterna av problemen. Som en enkel corollary presenterar vi en algoritm som ger en graf G bygger en subgraf med Õ(n) kanter och stretch avgränsas av träd stretch av G, nämligen den minsta maximala sträcka av ett spanning träd för G. Analysen av våra algoritmer innebär den nya uppfattningen om kantdominerande system som utvecklats i papperet. Den teknik som introduceras i tidningen minskar de studerade algoritmiska approximabilitetsfrågorna på k-spanners till rent grafteoretiska frågor om förekomsten av vissa kombinatoriska objekt i familjer av grafer.
Det relaterade problemet med graf sparifiering har också studerats väl i teorigemenskapen under begreppet "spanners" REF.
Approximating k-spanner problems for k > 2
{'venue': 'In Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}