Jan van den Heuvel
The External Network Problem with edge- or arc-connectivity requirements
van den Heuvel, Jan; Johnson, Matthew
Authors
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 |
Files
Accepted Conference Proceeding
(218 Kb)
PDF
Copyright Statement
The final publication is available at Springer via https://doi.org/10.1007/11527954_11
You might also like
Independent transversals versus transversals
(2019)
Conference Proceeding
Connected vertex cover for (sP1+P5)-free graphs
(2019)
Journal Article
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Finding a small number of colourful components
(2019)
Conference Proceeding
Clique-width for hereditary graph classes
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search