Multicommodity flow approximation used for exact graph partitioning

DOI10.1007/B13632zbMATH Open1266.68232OpenAlexW1827234103MaRDI QIDQ5897290FDOQ5897290

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

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

Mathematics Subject Classification ID

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

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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing and Combinatorics
• Title not available (Why is that?)
• 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)