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).
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|
|Full text:||(AM) Accepted Manuscript|
Download PDF (214Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/11527954_11|
|Publisher statement:||The final publication is available at Springer via https://doi.org/10.1007/11527954_11|
|Record Created:||28 Oct 2008|
|Last Modified:||30 Mar 2017 12:34|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Look up in GoogleScholar | Find in a UK Library|