We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

# The external network problem with edge- or arc-connectivity requirements.

van den Heuvel, J. and Johnson, M. (2005) 'The external network problem with edge- or arc-connectivity requirements.', in Combinatorial and algorithmic aspects of networking : first workshop on combinatorial and algorithmic aspects of networking, CAAN 2004, Banff, Alberta, Canada, August 5-7, 2004 ; revised selected papers. Berlin: Springer, pp. 114-126. Lecture notes in computer science. (3405).

## Abstract

The connectivity of a communications network can often be enhanced if the nodes are able, at some expense, to form links using an external network. In this paper, we consider the problem of how to obtain a prescribed level of connectivity with a minimum number of nodes connecting to the external network. Let D = (V,A) be a digraph. A subset X of vertices in V may be chosen, the so-called external vertices. An internal path is a normal directed path in D; an external path is a pair of internal paths p1=v1 ⋯ vs, p2=w1 ⋯ wt in D such that vs and w1 are external vertices ( the idea is that v1 can contact wt along this path using an external link from vt to w1 ). Then (D,X) is externally-k-arc-strong if for each pair of vertices u and v in V, there are k arc-disjoint paths ( which may be internal or external ) from u to v. We present polynomial algorithms that, given a digraph D and positive integer k, will find a set of external vertices X of minimum size subject to the requirement that (D,X) must be externally-k-arc-strong.

Item Type: Book chapter PDF - Accepted Version (214Kb) Peer-reviewed http://dx.doi.org/10.1007/11527954_11 The final publication is available at Springer via http://dx.doi.org/10.1007/11527954_11 28 Oct 2008 11 Dec 2015 09:38

 Social bookmarking: Export: EndNote, Zotero | BibTex Usage statistics Look up in GoogleScholar | Find in a UK Library