Integral flow decomposition with minimum longest path length

DOI10.1016/J.EJOR.2015.06.012MaRDI QIDQ320005zbMATH OpenOpenAlexFDO

Authors Krzysztof Pieńkosz, Kamil Kołtyś

Publication date 6 October 2016

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2015.06.012

zbMATH Keywords

networksapproximation algorithmsflow decompositionintegral flowNP-hard problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Recommendations

• scientific article; zbMATH DE number 3950169
• Flow Decomposition with Subpath Constraints
• scientific article; zbMATH DE number 7121921
• Simple bounds and greedy algorithms for decomposing a flow into a minimal set of paths
• Integer version of the multipath flow network synthesis problem
• Multiflows and disjoint paths of minimum total cost
• scientific article; zbMATH DE number 6304483
• A mixed integer programming approach for the minimum maximal flow
• Solving the minimum flow problem with interval bounds and flows
• A Dacorogna-Moser approach to flow decomposition and minimal flow problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2150800 (Why is no real title available?)
• An improved algorithm for decomposing arc flows into multipath flows
• Introduction to algorithms.
• Network flows. Theory, algorithms, and applications.
• Simple bounds and greedy algorithms for decomposing a flow into a minimal set of paths
• The complexity of finding two disjoint paths with min-max objective function

Cited in

(3)

• Feasibility of flow decomposition with subpath constraints in linear time
• Safety and completeness in flow decompositions for RNA assembly
• Simple bounds and greedy algorithms for decomposing a flow into a minimal set of paths

This page was built for publication: Integral flow decomposition with minimum longest path length

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