The complexity of the network design problem

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory to circuits and networks (94C15) Applications of design theory to circuits and networks (94C30)

Cites Work

Title not available (Why is that?)
`` Strong NP-Completeness Results

Cited In (87)

Algorithms for the optimum communication spanning tree problem
The zoo of tree spanner problems
MAD trees and distance-hereditary graphs
Network design for time-constrained delivery using subgraphs
A survey of the all-pairs shortest paths problem and its variants in graphs
Models for planning capacity expansion in local access telecommunication networks
Flots entiers et multiflots fractionnaires couplés par une contrainte de capacité
On the stability properties of linear dynamic time-varying unforced systems involving switches between parameterizations from topologic considerations via graph theory
Multi-source spanning trees: Algorithms for minimizing source eccentricities.
A decomposition method for the min concave cost flow problem with a staircase structure
Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs
Memetic algorithms
A GRASP and path relinking heuristic for rural road network development
Spanning trees: A survey
The tree of hubs location problem
Worst-Case Analysis of Network Design Problem Heuristics
A dual ascent approach to the fixed-charge capacitated network design problem
Lagrangean relaxation heuristics for the \(p\)-cable-trench problem
Memory-efficient enumeration of constrained spanning trees
Flow network design for manufacturing systems layout
Cross-facility management of production and transportation planning problem
Communication tree problems
Exact algorithms for minimum routing cost trees
Combinatorial network abstraction by trees and distances
An improved algorithm for the \(k\)-source maximum eccentricity spanning trees
Low complexity variants of the arrow distributed directory
The complexity of minimizing certain cost metrics for \(k\)-source spanning trees.
A branch-price-and-cut algorithm for the minimum evolution problem
Combined column-and-row-generation for the optimal communication spanning tree problem
A new optimal algorithm for backbone topology design in communications networks
Multi-objective routing within large scale facilities using open finite queueing networks
Network design for time‐constrained delivery
On the balanced minimum evolution polytope
Models and algorithms for network reduction
Modeling and optimization of buffers and servers in finite queueing networks
Extremal values for ratios of distances in trees
Average distance and connected domination
Design and implementation of a decision support system for multistage investment in Chinese coal production and transportation
Approximation algorithms for the shortest total path length spanning tree problem
Finding best swap edges minimizing the routing cost of a spanning tree
Title not available (Why is that?)
The minimum flow cost Hamiltonian cycle problem: a comparison of formulations
Exact approaches for the minimum subgraph diameter problem
Minimax flow tree problems
Lagrangean bounds for the optimum communication spanning tree problem
A variable fixing heuristic with local branching for the fixed charge uncapacitated network design problem with user-optimal flow
Average distance, minimum degree, and spanning trees
Solving network design problems via iterative aggregation
Buffer and server allocation in general multi-server queueing networks
Modelling and simulation of communications network planning
An exact approach for the multicommodity network optimization problem with a step cost function
Approximation algorithms for some optimum communication spanning tree problems
On the intercluster distance of a tree metric
On the complexity of edge labelings for trees
Approximation algorithms for the optimal \(p\)-source communication spanning tree
LARGE SCALE NETWORK ARCHITECTURE SYNTHESIS: INTERACTIVE STRATEGY
Light graphs with small routing cost
Complexity of spanning tree problems: Part I
A tutorial on the balanced minimum evolution problem
A decomposition method using a pricing mechanism for min concave cost flow problems with a hierarchical structure
On the tree conjecture for the network creation game
A linear-time algorithm to compute a MAD tree of an interval graph
On the minimum average distance spanning tree of the hypercube
Solving the optimal network problem
Exact algorithms based on Benders decomposition for multicommodity uncapacitated fixed-charge network design
Multiple allocation tree of hubs location problem for non-complete networks
An initial study of budgeted Steiner networks
Lower bounding techniques for the degree-constrained network design problem
Geometric spanning trees minimizing the Wiener index
NeuroPrim: an attention-based model for solving NP-hard spanning tree problems
Geometric Network Creation Games
Bounded-degree light approximate shortest-path trees in doubling metrics
New valid inequalities for the optimal communication spanning tree problem
OVERALL DESIGN OF RELIABLE CENTRALIZED VOICE/DATA COMMUNICATION NETWORK
A PTAS for the metric case of the minimum sum-requirement communication spanning tree problem
A PTAS for the metric case of the optimum weighted source-destination communication spanning tree problem
An approach to the distributionally robust shortest path problem
Minimum average distance clique trees
Proof of a conjecture about minimum spanning tree cycle intersection
Hardness and approximation for the star \(p\)-hub routing cost problem in metric graphs
Social distancing network creation
On the average distance of the hypercube tree
Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded below
Geometric spanning trees minimizing the Wiener index
Multi-shuttle crane scheduling in automated storage and retrieval systems
The minimum routing cost tree problem. State of the art and a core-node based heuristic algorithm
Demand-aware network designs of bounded degree

This page was built for publication: The complexity of the network design problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4178943)