En t-spanner av en graf G är dess spännvidd subgraf S sådan att avståndet mellan varje par av hörn i S är som mest t gånger deras avstånd i G. Den glesaste t-spanner problem ber att hitta, för en given graf G och ett heltal t, en t-spanner av G med minsta antal kanter. Problemet är känt för att vara NP-hård för alla t ≥ 2, och, ännu mer, är det NP-hård att approximera det med förhållandet O(log n) för varje t ≥ 2. För t ≥ 5, är problemet fortfarande NP-hård för planar grafer och ungefärlighet status för problemet på planar grafer var öppen. Vi löser denna öppna fråga genom att visa att det glesaste t-spanner problemet medger effektiva polynom tid approximation systemet (EPTAS) för varje t ≥ 1. Vårt resultat håller för en mycket bredare klass av grafer, nämligen den klass av apex-minorfria grafer, som innehåller klasser av planar och avgränsade genus grafer. Dessutom är det möjligt att utvidga våra resultat till viktade apex-minor fria grafer, när den maximala kanten vikt begränsas av vissa konstant.
Dragan m.fl. REF gav en EPTAS för problemet i plana diagram.
Approximation of minimum weight spanners for sparse graphs
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}