DIMACS

Center for Discrete Mathematics & Theoretical Computer Science

DIMACS EDUCATIONAL MODULE SERIES

MODULE 03-5 Communications Network Design^{1}

Date prepared: October 17, 2003

Steven Cosares Hofstra University, Hempstead, New York 11549

Fred Rispoli Dowling College, Oakdale, New York 11769

DIMACS Center, CoRE Bldg., Rutgers University, 96 Frelinghuysen Road, Piscataway, NJ 08854-8018

TEL: 732-445-5928 • FAX: 732-445-5932 • EMAIL: center@dimacs.rutgers.edu

                         Web: http://dimacs.rutgers.edu/

Founded as a National Science Foundation Science and Technology Center and a Joint Project of Rutgers University, Princeton University, AT&T Labs - Research, Bell Labs, NEC Laboratories America and Telcordia Technologies with affiliated members Avaya Labs, HP Labs, IBM Research, Microsoft Research.

1Research supported by NSF Grant DUE 97-52776

Module Description Information

• Title:

Communications Network Design

• Author(s):

Steven Cosares, Hofstra University, acsstc@hofstra.edu Fred Rispoli, Dowling College, rispolif@dowling.edu

• Abstract:

The module introduces students to a version of the Network Design problem (NDP) that arises in the planning for communication networks. A fixed cost is usually associated with placing or activating the link between some pair of nodes. The variable cost associated with a link is proportional to the number of connections supported by the link. The objective in NDP is to find a spanning tree for which the total of the fixed and variable costs is minimized.

• Informal Description:

The module covers some of the basic ideas motivating the use of heuristic solution techniques when an optimal solution is difficult to find. It uses the relatively simple solution techniques for the shortest paths and minimum spanning tree problems as frameworks for generating solutions to this complex problem.

• Target Audience:

The module is intended for undergraduate or graduate students taking a course involving either Discrete Mathematics, Network Flows, Integer Programming, or Optimization.

• Prerequisites:

The module is designed for students that have been introduced to some basic concepts of networks, including the Shortest Paths problem and the Minimum Spanning Tree problem.

• Mathematical Field:

Discrete Mathematics, Network Flows, Algorithms, Mathematical Programming

• Applications Areas:

Telecommunications, Networking, Transportation

• Mathematics Subject Classification:

Primary 90C35; Secondary 65K05

• Contact Information:

Steven Cosares Hofstra University, Hempstead, New York 11549 email: Steven.T.Cosares@Hofstra.edu

• Other DIMACS modules related to this module: None