Polynomial-time algorithms for special cases of the maximum confluent flow problem

DOI10.1016/J.DAM.2013.07.012MaRDI QIDQ2434729zbMATH OpenOpenAlexFDO

Authors Daniel Dressler, Martin Strehler

Publication date 7 February 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2013.07.012

zbMATH Keywords

confluent flowFPTASouterplanar graphpolynomial-time algorithmtreewidth

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Flows in graphs (05C21) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Capacitated Confluent Flows: Complexity and Algorithms
• Meet and merge: approximation algorithms for confluent flows
• Meet and merge: approximation algorithms for confluent flows
• (Almost) tight bounds and existence theorems for confluent flows
• (Almost) Tight bounds and existence theorems for single-commodity confluent flows

Cites work

• (Almost) Tight bounds and existence theorems for single-commodity confluent flows
• A TREE PARTITIONING PROBLEM ARISING FROM AN EVACUATION PROBLEM IN TREE DYNAMIC NETWORKS
• Capacitated Confluent Flows: Complexity and Algorithms
• Easy problems for tree-decomposable graphs
• scientific article; zbMATH DE number 6845150 (Why is no real title available?)
• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• scientific article; zbMATH DE number 3259770 (Why is no real title available?)
• Linear algorithms to recognize outerplanar and maximal outerplanar graphs
• Maximal Flow Through a Network
• Meet and merge: approximation algorithms for confluent flows
• Routing and capacity optimization for IP networks

Cited in

(11)

• A faster polynomial algorithm for the constrained maximum flow problem
• Exact solution algorithms for the maximum flow problem with additional conflict constraints
• Meet and merge: approximation algorithms for confluent flows
• The maximum flow problem with conflict and forcing conditions
• Capacitated Confluent Flows: Complexity and Algorithms
• Approximation Algorithms for the Maximum Concurrent Flow Problem
• scientific article; zbMATH DE number 871948 (Why is no real title available?)
• scientific article; zbMATH DE number 1418332 (Why is no real title available?)
• Non-approximability and polylogarithmic approximations of the single-sink unsplittable and confluent dynamic flow problems
• scientific article; zbMATH DE number 6402605 (Why is no real title available?)
• The Maximum Flow Problem for Oriented Flows

This page was built for publication: Polynomial-time algorithms for special cases of the maximum confluent flow problem

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