Counting and sampling minimum (s, t)-cuts in weighted planar graphs in polynomial time

被引：7

作者：

Bezakova, Ivona ^{[1
]}

Friedlander, Adam J. ^{[2
]}

机构：

[1] Rochester Inst Technol, Rochester, NY 14623 USA

[2] IBM Corp, Poughkeepsie, NY USA

来源：

THEORETICAL COMPUTER SCIENCE | 2012年 / 417卷

关键词：

Counting and sampling; Minimum; (s; t)-cuts; Weighted planar graphs; Maximum flow; Maximal antichains in partially ordered sets; CUTS; NETWORK;

D O I：

10.1016/j.tcs.2011.05.017

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We give an O(nd + n log n) algorithm computing the number of minimum (s, t)-cuts in weighted planar graphs, where n is the number of vertices and d is the length of the shortest s-t path in the corresponding unweighted graph. Previously, Ball and Provan gave a polynomial-time algorithm for unweighted planar graphs with both s and t lying on the outer face. Our results hold for all locations of s and t and weighted graphs, and have direct applications in computer vision. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：2 / 11

页数：10

共 20 条

[1]

[Anonymous], 2005, Algorithm Design

[2]

[Anonymous], 2001, Interactive Graph Cuts, DOI DOI 10.1109/ICCV.2001.937505

[3]

[Anonymous], 2006, MATH MODELS C VISION

[4] CALCULATING BOUNDS ON REACHABILITY AND CONNECTEDNESS IN STOCHASTIC NETWORKS [J].