A NOTE ON MULTIFLOW LOCKING THEOREM

スポンサーリンク

概要

• 論文の詳細を見る

• This note addresses the undirected multiflow (multicommodity flow) theory. A multiflow in a network with terminal set T can be regarded as a single commodity (A,T＼A)-flow for any nonempty proper subset A⊂T by ignoring flows not connecting A and T＼A. A set system A on T is said to be lockable if for every network having T as terminal set there exists a multiflow being simultaneously a maximum (A,T＼A)-flow for every A∈A. The multiflow locking theorem, due to Karzanov and Lomonosov, says that A is lockable if and only if it is 3-cross-free. A multiflow can also be regarded as a single commodity (A,B)-flow for every partial cut (A,B) of terminals, where a partial cut is a pair of disjoint subsets (not necessarily a bipartition). Based on this observation, we study the locking property for partial cuts, and prove an analogous characterization for a lockable family of partial cuts.

著者

• Hirai Hiroshi

  Research Institute For Mathematical Sciences Kyoto University

関連論文

• A NOTE ON MULTIFLOW LOCKING THEOREM
• M-Convex Functions and Tree Metrics
• Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees (コンピュテーション)

スポンサーリンク