Given a graph G with m edges and n nodes, a spanning tree T of G, and an edge e that is being deleted from or inserted into G, we give efficient O(n) algorithms to compute a possible swap for e that minimizes the diameter of the new spanning tree. This problem arises in high-speed networks, particularly in optical networks.
Italiano, Giuseppe Francesco; Ramaswami, R.. (1998). Maintaining spanning trees of small diameter. ALGORITHMICA, (ISSN: 0178-4617), 22: 275-304.
Maintaining spanning trees of small diameter
ITALIANO G;
1998
Abstract
Given a graph G with m edges and n nodes, a spanning tree T of G, and an edge e that is being deleted from or inserted into G, we give efficient O(n) algorithms to compute a possible swap for e that minimizes the diameter of the new spanning tree. This problem arises in high-speed networks, particularly in optical networks.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
