%0 Journal Article
%T Max-Flow Problem in Undirected Planar Networks with Node Capacities Being in NC
%A Xian-Chao Zhang
%A Ying-Yu Wan
%A Guo-Liang Chen
%A <br>Xian-ChaoZhang
%A Ying-YuWan
%A Guo-LiangChen
%J 计算机科学技术学报
%D 2004
%I 
%X The max-flow problem in planar networks with only edge capacities has been proved to be in NC (Nickle's Class). This paper considers a more general version of the problem when the nodes as well as the edges have capacities. In a general network, the node-edge-capacity problem can be easily reduced to the edge-capacity problem. But in the case of planar network this reduction may destroy the planarity, and reduces the problem to the edge-capacity problem in a general network, which is P-complete. A recent contribution presents a new reduction for planar networks, that maintains the planarity. In this paper, it is proved that this reduction is in NC and thus the node-edge-capacity problem in undirected planar networks is in NC.
%K parallel algorithm
%K NC (Nickle's Class) algorithm
%K max-flow<br>最大流量
%K NC
%K 网络节点
%K 并行算法
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=8A0BB7018C74A84ACF4546183A0FD883&yid=D0E58B75BFD8E51C&vid=2A8D03AD8076A2E3&iid=B31275AF3241DB2D&sid=2B25C5E62F83A049&eid=2B25C5E62F83A049&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=0&reference_num=11