# AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution

# Network Design: Connectivity and Facilities Location

### About this Title

**Panos M. Pardalos** and **Dingzhu Du**, Editors

Publication: DIMACS Series in Discrete Mathematics and Theoretical Computer Science

Publication Year:
1998; Volume 40

ISBNs: 978-0-8218-0834-4 (print); 978-1-4704-3998-9 (online)

DOI: https://doi.org/10.1090/dimacs/040

MathSciNet review: MR1612993

MSC: Primary 68-06; Secondary 00B25, 05-06, 90-06

### Table of Contents

**Front/Back Matter**

**Chapters**

- Nearly linear time approximation schemes for Euclidean TSP and other geometric problems
- Differential greedy for the 0–1 equicut problem
- Gradient-constrained minimal Steiner trees
- The Steiner tree problem for terminals on the boundary of a rectilinear polygon
- Using Hadwiger numbers in network design
- Reducing the graphical Steiner problem with a sensitivity test
- A frequency assignment problem in cellular phone networks
- An optimal greedy algorithm for wavelength allocation in directed tree networks
- A GRASP algorithm for the single source uncapacitated minimum concave-cost network flow problem
- Approximation results for the optimum cost chromatic partition problem
- Approximating dense cases of covering problems
- Connected facility location problems
- Constrained spanning tree problems: Approximate methods and parallel computation
- Star, grid, ring topologies in facility location & network design
- Network improvement problems
- Improved results on service-constrained network design problems
- A greedy randomized adaptive search procedure for the multitarget multisensor tracking problem
- A generalized threshold algorithm for the shortest path problem with time windows
- A case study of de-randomization methods for combinatorial approximation algorithms
- A chunking based genetic algorithm for the Steiner tree problem in graphs
- A new exact algorithm for rectilinear Steiner trees
- A scalable TWDM lightwave network based on generalized de Bruijn digraph
- A new model of generalized Steiner trees and 3-coordinate systems
- A model for network design
- Nonlinear and mixed-integer optimization in chemical process network systems
- Shortest networks on spheres