En t-spanner av en graf G är en spännvidd subgraf H sådan att avståndet mellan två hörn i H är som mest t gånger deras avstånd i G. Spannrar uppstår i samband med approximering av den ursprungliga grafen genom en gles subgraf 23]. Minimum t-SPANNER problemet syftar till att nd en t-spanner med det minsta antalet kanter för den givna grafen. I detta papper, vi helt avgöra komplexiteten status detta problem för olika värden av t, på Chordal grafer, Split grafer, Bipartite grafer och Convex Bipartite grafer. Våra resultat avgör en öppen fråga som togs upp i 7] och förenklar också avsevärt några av de bevis som lades fram i 7, 8]. Vi ger också en faktor två approximation algoritm för minimum 2-SPANNER problem på intervall grafer. Slutligen tillhandahåller vi approximationsalgoritmer för bandbreddsminimering problem på Convex Bipartite grafer och Split grafer med hjälp av begreppet träd skiftnycklar.
Venkatesan m.fl. REF avslöjade komplexiteten i minsta multiplikativa t-pannerproblem för flera grafklasser såsom ackordsgrafer, konvexa bipartitgrafer och delade grafer.
Restrictions of Minimum Spanner Problems
{'venue': 'Inf. Comput.', 'journal': 'Inf. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}