MINIMUM CUTS AND SHORTEST CYCLES IN DIRECTED PLANAR. GRAPHS VIA NONCROSSING SHORTEST PATHS

Liang, HC; Lu, HI

Lu, HI (reprint author), Natl Taiwan Univ, Dept Comp Sci & Informat Engn, Taipei, Taiwan.

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2017; 31 (1): 454

Abstract

Let G be an n-node simple directed planar graph with nonnegative edge weights. We study the fundamental problems of computing (1) a global cut of G wi......

Full Text Link