Vi undersöker ett problem med nätverksdesignen enligt reload cost-modellen. Med tanke på en oriktad kant färgad graf, uppladdningskostnader på en stig uppstår vid en nod där sökvägen använder på varandra följande kanter av olika färger. Vi anser att problemet med att ta bort ett träd med minsta diameter när det gäller kostnaderna för att lasta om. Vi presenterar nedre gränser för approximabilitet även på grafer med maximal grad 5. Å andra sidan ger vi en exakt algoritm för grafer av maximal grad 3.?
I REF, författarna anser problemet med att hitta ett spännträd med minsta diameter med avseende på reload kostnader och de föreslår ojämförligt resultat för grafer av maximal grad 5 och polynom resultat för grafer av maximal grad 3.
Reload cost problems: minimum diameter spanning tree
{'venue': 'Discret. Appl. Math.', 'journal': 'Discret. Appl. Math.', 'mag_field_of_study': ['Computer Science']}