TR-2001-07

Combined connectivity augmentation and orientation problems

András Frank, Tamás Király

Published in:
Discrete Applied Mathematics 131 (2003), 401-419.



Abstract

Two important branches of graph connectivity problems are connectivity augmentation, which consists of augmenting a graph by adding new edges so as to meet a specified target connectivity, and connectivity orientation, where the goal is to find an orientation of an undirected or mixed graph that satisfies some specified edge-connection property. In the present work an attempt is made to link the above two branches, by considering degree-specified and minimum cardinality augmentation of graphs so that the resulting graph admits an orientation satisfying a prescribed edge-connection requirement, such as (k,l)-edge-connectivity. The results are obtained by combining the supermodular polyhedral methods used in connectivity orientation with the splitting off operation, which is a standard tool in solving augmentation problems.


Keywords:
Graph, Orientation, Connectivity augmentation, Supermodularity


Bibtex entry:

@techreport{egres-01-07,
AUTHOR = {Frank, Andr{\'a}s and Kir{\'a}ly, Tam{\'a}s},
TITLE = {Combined connectivity augmentation and orientation problems},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2001},
NUMBER = {TR-2001-07}
}


Last modification: 15.9.2018. Please email your comments to Tamás Király!