The maximum flow problem with disjunctive constraints

DOI10.1007/S10878-011-9438-7MaRDI QIDQ358660zbMATH OpenOpenAlexWikidataFDO

Authors Ulrich Pferschy, Joachim Schauer

Publication date 9 August 2013

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-011-9438-7

zbMATH Keywords

maximum flow problemconflict graphbinary constraints

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• The maximum flow problem with conflict and forcing conditions
• The maximum concurrent flow problem
• The Maximum Integer Multiterminal Flow Problem
• Maximum flows on disjoint paths
• scientific article; zbMATH DE number 6863577
• A new approach to the maximum-flow problem
• The maximum flow problem: A max-preflow approach
• Exact solution algorithms for the maximum flow problem with additional conflict constraints
• Flow maximization problem as linear programming problem with capacity constraints
• A maximum flow problem with intermediate node requirements

Cites work

• scientific article; zbMATH DE number 432789 (Why is no real title available?)
• scientific article; zbMATH DE number 3906193 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1333600 (Why is no real title available?)
• An approximation scheme for bin packing with conflicts
• Approximation algorithms for time constrained scheduling
• Network flows. Theory, algorithms, and applications.
• On the structure of all minimum cuts in a network and applications
• Optimization, approximation, and complexity classes
• Paths, trees and matchings under disjunctive constraints
• The Knapsack Problem with Conflict Graphs
• The maximum flow problem with conflict and forcing conditions
• The minimum spanning tree problem with conflict constraints and its variations
• The transportation problem with exclusionary side constraints

Cited in

(31)

• Parameterized complexity of conflict-free matchings and paths
• Approximation of knapsack problems with conflict and forcing graphs
• Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach
• The transportation problem with conflicts
• The maximum flow problem with conflict and forcing conditions
• Conflict free version of covering problems on graphs: classical and parameterized
• Exact solution algorithms for the maximum flow problem with additional conflict constraints
• Solving the set covering problem with conflicts on sets: a new parallel GRASP
• A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs
• A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints
• The Red-Blue transportation problem
• Robust transshipment problem under consistent flow constraints
• Set covering problem with conflict constraints
• Minimum cost flow problem with conflicts
• Secondary structure ensemble analysis via community detection
• On the maximum acyclic subgraph problem under disjunctive constraints
• Exploring the kernelization borders for hitting cycles
• Robust minimum cost flow problem under consistent flow constraints
• A unifying model for locally constrained spanning tree problems
• Assignment problem with conflicts
• scientific article; zbMATH DE number 6863577 (Why is no real title available?)
• Parameterized complexity of conflict-free matchings and paths
• Maximum weight perfect matching problem with additional disjunctive conflict constraints
• Cable tree wiring -- benchmarking solvers on a real-world scheduling problem with a variety of precedence constraints
• Paths, trees and matchings under disjunctive constraints
• A maximum flow problem with intermediate node requirements
• Fair allocation of indivisible items with conflict graphs
• A branch and cut algorithm for minimum spanning trees under conflict constraints
• Maximum weighted matching with few edge crossings for 2-layered bipartite graph
• Minimum cost noncrossing flow problem on layered networks
• Scott: shape-location combined tracking with optimal transport

This page was built for publication: The maximum flow problem with disjunctive constraints

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