Minsta routingkostnad spannträd
Inom datavetenskap är den minsta routingkostnaden som sträcker sig över trädet i en viktad graf ett spännträd som minimerar summan av parvisa avstånd mellan hörn i trädet. Det kallas också för det optimala avståndsöverspänningsträdet , det kortaste totala banlängdsspänningsträdet , det minsta totala avståndsspänningsträdet eller det minsta genomsnittliga avståndsöverträdet . I en oviktad graf är detta spännträdet för lägsta Wienerindex . Hu (1974) skriver att problemet med att konstruera dessa träd föreslogs av Francesco Maffioli.
Det är NP-svårt att konstruera det, även för oviktade grafer. Den har dock ett approximationsschema för polynom-tid . Approximationen fungerar genom att välja ett tal som beror på approximationsförhållandet men inte på antalet hörn i inmatningsgrafen, och genom att söka bland alla träd med interna noder.
Den lägsta routingkostnaden som spänner över trädet för en oviktad intervallgraf kan konstrueras i linjär tid. En polynomtidsalgoritm är också känd för ärftliga avståndsgrafer, viktade så att de viktade avstånden är ärftliga.