Very Simple Methods for All Pairs Network Flow Analysis

DOI10.1137/0219009zbMath0711.90023OpenAlexW1986207529MaRDI QIDQ3496127

Dan Gusfield

Publication date: 1990

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0219009

zbMATH Keywords

oraclemaximum network flowcut tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35) Deterministic network models in operations research (90B10) Graph theory (05C99) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (32)

Dynamic programming and graph optimization problems ⋮ Tight Bounds for Gomory-Hu-like Cut Counting ⋮ An algorithm for computing maximum solution bases ⋮ On the collaboration uncapacitated arc routing problem ⋮ Design of survivable IP-over-optical networks ⋮ Mincut sensitivity data structures for the insertion of an edge ⋮ Multi-depot rural postman problems ⋮ TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration ⋮ Continuous maximal covering location problems with interconnected facilities ⋮ Efficient Algorithm for Computing All Low s-t Edge Connectivities in Directed Graphs ⋮ Computational comparisons of different formulations for the Stackelberg minimum spanning tree game ⋮ Some insights on dynamic maintenance of Gomory-Hu tree in cactus graphs and general graphs ⋮ On a Special Co-cycle Basis of Graphs ⋮ Ancestor tree for arbitrary multi-terminal cut functions ⋮ Mincut Sensitivity Data Structures for the Insertion of an Edge ⋮ Revisiting parametric multi-terminal problems: maximum flows, minimum cuts and cut-tree computations ⋮ On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms ⋮ Speeding up the Gomory-Hu parallel cut tree algorithm with efficient graph contractions ⋮ Ordered weighted average optimization in multiobjective spanning tree problem ⋮ Minimum cut bases in undirected networks ⋮ A branch-and-cut algorithm for the k-edge connected subgraph problem ⋮ Designing multi-commodity flow trees ⋮ Coordinating resources in Stackelberg security games ⋮ Optimizing compatible sets in wireless networks through integer programming ⋮ Extracting maximal information about sets of minimum cuts ⋮ Dynamic Graph Clustering Using Minimum-Cut Trees ⋮ Parametric analysis on cut-trees and its application on a protein clustering problem ⋮ Properties of Gomory-Hu co-cycle bases ⋮ On spanning tree congestion of graphs ⋮ Unnamed Item ⋮ Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut ⋮ Designing multi-commodity flow trees

This page was built for publication: Very Simple Methods for All Pairs Network Flow Analysis