Ridurre al minimo la distanza totale utilizzando k collegamenti tra n nodi

Question

Mi è venuto in mente il seguente problema che non conosco le soluzioni e non riesco a trovare il termine di ricerca per approfondire.

Supponiamo di avere N nodi ordinati (n_1, n_2 .... n_N) ciascuno con una distanza fissa di 1 tra di loro. Quindi dist (n_1, n_N) = N-1. Ora siamo autorizzati a collegare due nodi qualsiasi, riducendo così efficacemente la loro distanza a 1. Supponiamo di poter avere k tali connessioni.

Il problema è: come scegliere quali nodi collegare per minimizzare la distanza totale tra due nodi?

Questo problema è una variante nota di alcuni problemi ben studiati? Ha una soluzione efficiente esiste per questo (o una variante in cui vogliamo solo ridurre al minimo la distanza massima tra due nodi)

Grazie

Answer 1

Potresti essere interessato a "On the sum of all distances in a graph or digraph". Quella carta si riferisce alla tua "distanza totale" come "trasmissione" di un grafico. La tua "distanza massima" viene generalmente chiamata il "diametro" di un grafico. Discute le due, dimostra alcune proprietà della trasmissione di un grafico e mostra che la trasmissione e il diametro sono indipendenti l'uno dall'altro.

Ingenuamente, hai le opzioni n-choose-k da provare. È piuttosto brutto se n e k sono grandi. Non male se uno di questi è piccolo.

C'è del lavoro per fare meglio di così. This Mathoverflow question chiede di ridurre la distanza media tra i vertici, che è proporzionale alla trasmissione del grafico. Ci sono due risposte, nessuna delle quali posso garantire. Si riferisce anche a a paper che risponde direttamente a questa domanda.

La riduzione al minimo del diametro di un grafico viene gestita in this paper.

Si potrebbe prendere in considerazione l'indirizzo di questa domanda per il Math stackexchange.