Optimum Communication Spanning Trees

DOI10.1137/0203015zbMath0269.90010OpenAlexW2047517090MaRDI QIDQ3212880

No author found.

Publication date: 1974

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/94490d5619b4d9ada27cde9df5b1a6a1b8c96c63

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Related Items (55)

Tight bounds from a path based formulation for the tree of hub location problem ⋮ Approximation algorithms for the optimal \(p\)-source communication spanning tree ⋮ An improved algorithm for the \(k\)-source maximum eccentricity spanning trees ⋮ Light graphs with small routing cost ⋮ Exact algorithms for minimum routing cost trees ⋮ A PTAS for the metric case of the optimum weighted source-destination communication spanning tree problem ⋮ Models and algorithms for network reduction ⋮ Reload cost trees and network design ⋮ Designing a road network for hazardous materials shipments ⋮ Combined column-and-row-generation for the optimal communication spanning tree problem ⋮ Optimization in telecommunication networks ⋮ On the intercluster distance of a tree metric ⋮ Proof of a conjecture about minimum spanning tree cycle intersection ⋮ When Do Gomory--Hu Subtrees Exist? ⋮ General network design: a unified view of combined location and network design problems ⋮ Hardness and approximation for the star \(p\)-hub routing cost problem in metric graphs ⋮ Optimal design of switched Ethernet networks implementing the multiple spanning tree protocol ⋮ Social distancing network creation ⋮ Geometric spanning trees minimizing the Wiener index ⋮ On the approximability of the minimum strictly fundamental cycle basis problem ⋮ The complexity of minimizing certain cost metrics for \(k\)-source spanning trees. ⋮ \(k\)-outerplanar graphs, planar duality, and low stretch spanning trees ⋮ On the complexity of edge labelings for trees ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Multi-source spanning trees: Algorithms for minimizing source eccentricities. ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ New Valid Inequalities for the Optimal Communication Spanning Tree Problem ⋮ Using Petal-Decompositions to Build a Low Stretch Spanning Tree ⋮ Bilinear matrix equation characterizes Laplacian and distance matrices of weighted trees ⋮ Bounded-degree light approximate shortest-path trees in doubling metrics ⋮ Solving the optimum communication spanning tree problem ⋮ Parallel construction of multiple independent spanning trees on highly scalable datacenter networks ⋮ Ordered weighted average optimization in multiobjective spanning tree problem ⋮ The zoo of tree spanner problems ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ Optimization realization of a distance matrix † ⋮ Unnamed Item ⋮ Minimax flow tree problems ⋮ Data analysis implications of some concepts related to the cuts of a graph ⋮ Communication tree problems ⋮ A tight bound on approximating arbitrary metrics by tree metrics ⋮ An algorithm for the most economic link addition in a tree communications network ⋮ Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links ⋮ Approximation algorithms for some optimum communication spanning tree problems ⋮ The minimum routing cost tree problem. State of the art and a core-node based heuristic algorithm ⋮ Unnamed Item ⋮ The tree of hubs location problem ⋮ Approximation algorithms for the shortest total path length spanning tree problem ⋮ Network design for time‐constrained delivery ⋮ The minimum flow cost Hamiltonian cycle problem: a comparison of formulations ⋮ Exact approaches for the minimum subgraph diameter problem ⋮ Low complexity variants of the arrow distributed directory ⋮ Compact vs. exponential-size LP relaxations ⋮ A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem

This page was built for publication: Optimum Communication Spanning Trees