Flows, cuts and integral routing in graphs -- an approximation algorithmist's perspective

MaRDI QIDQ4589020zbMATH OpenFDO

Authors Julia Chuzhoy

Publication date 6 November 2017

zbMATH Keywords

approximation algorithmsgraph theoryhardness of approximationmaximum flowminimum cutnetwork routing

Mathematics Subject Classification ID

Flows in graphs (05C21) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Recommendations

• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Algorithms for 2-Route Cut Problems
• Approximate max-integral-flow/min-multicut theorems
• Randomized approximation schemes for cuts and flows in capacitated graphs
• scientific article; zbMATH DE number 4204092

Cited in

(4)

• Multiroute flows: cut-trees and realizability
• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• Flows on few paths: Algorithms and lower bounds
• Vertex downgrading to minimize connectivity

This page was built for publication: Flows, cuts and integral routing in graphs -- an approximation algorithmist's perspective

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4589020)