The External Network Problem with edge- or arc-connectivity requirements

van den Heuvel, Jan; Johnson, Matthew

doi:10.1007/11527954_11

The External Network Problem with edge- or arc-connectivity requirements

van den Heuvel, Jan; Johnson, Matthew

Authors

Jan van den Heuvel

Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department

Contributors

A. López-Ortiz
Editor

A. Hamel
Editor

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.

Citation

van den Heuvel, J., & Johnson, M. (2005). The External Network Problem with edge- or arc-connectivity requirements. In A. López-Ortiz, & A. Hamel (Eds.), 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 (114-126). https://doi.org/10.1007/11527954_11

Conference Name	Combinatorial and Algorithmic Aspects of Networking (CAAN 2004)
Conference Location	Banff, Alberta, Canada
Start Date	Aug 5, 2004
End Date	Aug 7, 2004
Publication Date	Aug 1, 2005
Deposit Date	Oct 28, 2008
Publicly Available Date	Dec 11, 2015
Pages	114-126
Series Title	Lecture notes in computer science
Series Number	3405
Series ISSN	0302-9743,1611-3349
Book Title	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.
DOI	https://doi.org/10.1007/11527954_11
Public URL	https://durham-repository.worktribe.com/output/1162848