Graph orientations with set connectivity requirements

概要

論文の詳細を見る
In an undirected or a directed graph, the edge-connectivity between two disjoint vertex sets X and Y is defined as the minimum number of edges or arcs that should be removed for disconnecting all vertices in Y from those in X. This paper discusses how to construct a directed graph from a given undirected graph by orienting edges so as to preserve the edge-connectivity on pairs of vertex sets as much as possible. We present several bounds on the gap between the edge-connectivities in the undirected graph and in the obtained directed graphs, which extends the Nash-Williams’ strong orientation theorem.