Multicommodity flow approximation used for exact graph partitioning

DOI10.1007/B13632MaRDI QIDQ5897290zbMATH OpenOpenAlexFDO

Authors Meinolf Sellmann, Norbert Sensen, Larissa Timajev

Publication date 3 March 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b13632

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 1875431
• Fast approximation algorithms for multicommodity flow problems
• A polylogarithmic approximation of the minimum bisection
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Computing and Combinatorics

Cited in

(9)

• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
• An exact combinatorial algorithm for minimum graph bisection
• Simple probabilistic analysis to generalize bottleneck graph multi-partitioning
• scientific article; zbMATH DE number 139787 (Why is no real title available?)
• scientific article; zbMATH DE number 7286677 (Why is no real title available?)
• Computing and Combinatorics
• scientific article; zbMATH DE number 1875431 (Why is no real title available?)
• Applications of the Dulmage--Mendelsohn Decomposition and Network Flow to Graph Bisection Improvement
• ILP-Based Local Search for Graph Partitioning

This page was built for publication: Multicommodity flow approximation used for exact graph partitioning

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