×

Bicriteria network design problems. (English) Zbl 0906.68076

Summary: We study a general class of bicriteria network design problems. A generic problem in this class is as follows: Given an undirected graph and two minimization objectives (under different cost functions), with a budget specified on the first objective, find a subgraph from a given subgraph-class that minimizes the second objective subject to the budget on the first objective. We consider three different criteria – the total edge cost, the diameter, and the maximum degree of the network.

MSC:

68W10 Parallel algorithms in computer science
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv