The complexity of the network design problem
From MaRDI portal
Publication:4178943
DOI10.1002/net.3230080402zbMath0395.94048OpenAlexW2016218947MaRDI QIDQ4178943
Alexander H. G. Rinnooy Kan, David S. Johnson, Jan Karel Lenstra
Publication date: 1978
Published in: Networks (Search for Journal in Brave)
Full work available at URL: http://ageconsearch.umn.edu/record/272157
Analysis of algorithms and problem complexity (68Q25) Applications of design theory to circuits and networks (94C30) Applications of graph theory to circuits and networks (94C15)
Related Items
Worst-Case Analysis of Network Design Problem Heuristics, LARGE SCALE NETWORK ARCHITECTURE SYNTHESIS: INTERACTIVE STRATEGY, Memory-efficient enumeration of constrained spanning trees, 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 survey of the all-pairs shortest paths problem and its variants in graphs, A PTAS for the metric case of the optimum weighted source-destination communication spanning tree problem, Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs, A branch-price-and-cut algorithm for the minimum evolution problem, Models and algorithms for network reduction, Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded below, On the stability properties of linear dynamic time-varying unforced systems involving switches between parameterizations from topologic considerations via graph theory, Combined column-and-row-generation for the optimal communication spanning tree problem, A variable fixing heuristic with local branching for the fixed charge uncapacitated network design problem with user-optimal flow, On the intercluster distance of a tree metric, A decomposition method for the min concave cost flow problem with a staircase structure, Proof of a conjecture about minimum spanning tree cycle intersection, Extremal values for ratios of distances in trees, Average distance, minimum degree, and spanning trees, An approach to the distributionally robust shortest path problem, Multiple allocation tree of hubs location problem for non-complete networks, Lagrangean bounds for the optimum communication spanning tree problem, A tutorial on the balanced minimum evolution problem, Multi-shuttle crane scheduling in automated storage and retrieval systems, Hardness and approximation for the star \(p\)-hub routing cost problem in metric graphs, Minimum Average Distance Clique Trees, Solving the optimal network problem, Network design for time-constrained delivery using subgraphs, Demand-aware network designs of bounded degree, Social distancing network creation, Complexity of spanning tree problems: Part I, Geometric spanning trees minimizing the Wiener index, Geometric Network Creation Games, Average distance and connected domination, The complexity of minimizing certain cost metrics for \(k\)-source spanning trees., MAD trees and distance-hereditary graphs, On the complexity of edge labelings for trees, Unnamed Item, Modelling and simulation of communications network planning, Unnamed Item, Multi-source spanning trees: Algorithms for minimizing source eccentricities., New Valid Inequalities for the Optimal Communication Spanning Tree Problem, Multi-objective routing within large scale facilities using open finite queueing networks, Finding best swap edges minimizing the routing cost of a spanning tree, Spanning trees: A survey, On the minimum average distance spanning tree of the hypercube, Modeling and optimization of buffers and servers in finite queueing networks, A decomposition method using a pricing mechanism for min concave cost flow problems with a hierarchical structure, Bounded-degree light approximate shortest-path trees in doubling metrics, On the tree conjecture for the network creation game, Buffer and server allocation in general multi-server queueing networks, Combinatorial network abstraction by trees and distances, Flow network design for manufacturing systems layout, On the average distance of the hypercube tree, The zoo of tree spanner problems, Lagrangean relaxation heuristics for the \(p\)-cable-trench problem, Exact algorithms based on Benders decomposition for multicommodity uncapacitated fixed-charge network design, Cross-facility management of production and transportation planning problem, Unnamed Item, Lower bounding techniques for the degree-constrained network design problem, Minimax flow tree problems, Algorithms for the optimum communication spanning tree problem, Communication tree problems, Solving network design problems via iterative aggregation, Design and implementation of a decision support system for multistage investment in Chinese coal production and transportation, Flots entiers et multiflots fractionnaires couplés par une contrainte de capacité, A linear-time algorithm to compute a MAD tree of an interval graph, A dual ascent approach to the fixed-charge capacitated network design problem, 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, The tree of hubs location problem, An exact approach for the multicommodity network optimization problem with a step cost function, On the balanced minimum evolution polytope, Approximation algorithms for the shortest total path length spanning tree problem, Network design for time‐constrained delivery, A GRASP and path relinking heuristic for rural road network development, Memetic algorithms, OVERALL DESIGN OF RELIABLE CENTRALIZED VOICE/DATA COMMUNICATION NETWORK, A new optimal algorithm for backbone topology design in communications networks, The minimum flow cost Hamiltonian cycle problem: a comparison of formulations, Exact approaches for the minimum subgraph diameter problem, Models for planning capacity expansion in local access telecommunication networks, Low complexity variants of the arrow distributed directory, A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem
Cites Work
