Efficient algorithms for a simple network design problem

DOI10.1002/net.21500zbMath1338.68014OpenAlexW2043092513MaRDI QIDQ2811297

Takeaki Uno, Ryuhei Uehara, Shin-ichi Nakano

Publication date: 10 June 2016

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.21500

zbMATH Keywords

approximation algorithmNP-completenessefficient algorithmsmall-world networksimple network design

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Network design and communication in computer systems (68M10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Uses Software

• VRP

Cites Work

• A quadratic integer program for the location of interacting hub facilities
• The Vehicle Routing Problem
• Emergence of Scaling in Random Networks
• Algorithm for Single Allocation Problem on Hub-and-Spoke Networks in 2-Dimensional Plane
• The Structure and Function of Complex Networks
• The single allocation problem in the interacting three-hub network
• Collective dynamics of ‘small-world’ networks
• Unnamed Item
• Unnamed Item
• Unnamed Item