Skip navigation
Skip navigation

Flow equivalent trees in undirected node-edge-capacitated planar graphs

Zhang, Xianchou; Liang, Weifa; Jiang, He

Description

Given an edge-capacitated undirected graph G = (V, E, C) with edge capacity c : E {mapping} R+, n = | V |, an s - t edge cut C of G is a minimal subset of edges whose removal from G will separate s from t in the resulting graph, and the capacity sum of the edges in C is the cut value of C. A minimum s - t edge cut is an s - t edge cut with the minimum cut value among all s - t edge cuts. A theorem given by Gomory and Hu states that there are only n - 1 distinct values among the n (n - 1) / 2...[Show more]

CollectionsANU Research Publications
Date published: 2006
Type: Journal article
URI: http://hdl.handle.net/1885/32656
Source: Information Processing Letters
DOI: 10.1016/j.ipl.2006.06.001

Download

File Description SizeFormat Image
01_Zhang_Flow_equivalent_trees_in_2006.pdf373.18 kBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  20 July 2017/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator