DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE ODENSE UNIVERSITY Connectivity Augmentation Problems in Graphs Tibor Jordan CWI and Technical University Budapest Tuesday, March 28, 1995, at 2:15 PM The Seminar Room One of the fundamental problems in network design is to improve the reliability of a given network to a prescribed level by adding new links between existing nodes such that the cost/number of new links is as small as possible. The corresponding graph problem is to make a given (undirected or directed) graph k-(edge or vertex)-connected by adding a set of new edges with minimum cost/size for some connectivity requirement k. The weighted versions are usually NP-hard. For some of them efficient approximation algorithms are known. In this talk we will focus on the unweighted case where the number of new edges is to be minimized. There exist polynomial algorithms for most of these problems. The goal is to present recent results and some open questions in this area. (A graph (digraph) G=(V,E) is k-vertex-connected, if |V| >= k+1 and G-X is connected (strongly connected) for any subset X of V with |X| <= k-1. A graph (digraph) is said to be k-edge-connected, if G-F is connected (strongly connected) for any subset F of E with |F| <= k-1.) Joergen Bang-Jensen