On maximum flows in polyhedral domains

DOI10.1016/0022-0000(90)90020-LzbMath0705.68064MaRDI QIDQ918212

Joseph S. B. Mitchell

Publication date: 1990

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

shortest paths problems; computation of maximum flows

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90B10: Deterministic network models in operations research

52B70: Polyhedral manifolds

Related Items

Maximum thick paths in static and dynamic environments, Routing multi-class traffic flows in the plane

Cites Work

• Unnamed Item
• Unnamed Item
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• An algorithm for shortest-path motion in three dimensions
• Visibility of disjoint polygons
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• A sweepline algorithm for Voronoi diagrams
• An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
• Optimal shortest path queries in a simple polygon
• A data structure for dynamic trees
• The Discrete Geodesic Problem
• Maximal Flow Through a Network
• Maximal flow through a domain
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• A new approach to the maximum-flow problem
• Maximum Flow in Planar Networks
• Medial Axis Transformation of a Planar Shape
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems