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.
論文 | ランダム
- Working environment in a rubber sheet smoking factory polluted by smoke from biomass fuel burning and health influences to workers
- Study on Reinforcement of Damaged Box-Culverts with Post-Tensioning Prestress
- 『音樂利害』における「唱歌」の位置(2)
- サンプルとインスタンス--グッドマンの具体的例示概念を巡って
- 絶対の創失--音楽に見る近代--中等學校音楽教科書における《故郷》像の変遷(2)