The maximum flow problem with disjunctive constraints

DOI10.1007/s10878-011-9438-7zbMath1275.90120OpenAlexW2050524721WikidataQ61638321 ScholiaQ61638321MaRDI QIDQ358660

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

binary constraintsmaximum flow problemconflict graph

Mathematics Subject Classification ID

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

Related Items (27)

Minimum spanning tree with conflicting edge pairs: a branch-and-cut approach ⋮ The transportation problem with conflicts ⋮ The Red-Blue transportation problem ⋮ Set covering problem with conflict constraints ⋮ Secondary structure ensemble analysis via community detection ⋮ Parameterized complexity of conflict-free matchings and paths ⋮ Minimum cost noncrossing flow problem on layered networks ⋮ Robust minimum cost flow problem under consistent flow constraints ⋮ Minimum cost flow problem with conflicts ⋮ A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs ⋮ Maximum weight perfect matching problem with additional disjunctive conflict constraints ⋮ Robust transshipment problem under consistent flow constraints ⋮ Fair allocation of indivisible items with conflict graphs ⋮ Paths, trees and matchings under disjunctive constraints ⋮ On the maximum acyclic subgraph problem under disjunctive constraints ⋮ A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints ⋮ Exploring the Kernelization Borders for Hitting Cycles ⋮ Maximum weighted matching with few edge crossings for 2-layered bipartite graph ⋮ A branch and cut algorithm for minimum spanning trees under conflict constraints ⋮ Approximation of knapsack problems with conflict and forcing graphs ⋮ Assignment problem with conflicts ⋮ Exact solution algorithms for the maximum flow problem with additional conflict constraints ⋮ Unnamed Item ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ A unifying model for locally constrained spanning tree problems ⋮ Cable tree wiring -- benchmarking solvers on a real-world scheduling problem with a variety of precedence constraints ⋮ SCOTT: Shape-Location Combined Tracking with Optimal Transport

Cites Work

• The minimum spanning tree problem with conflict constraints and its variations
• Paths, trees and matchings under disjunctive constraints
• Approximation algorithms for time constrained scheduling
• The transportation problem with exclusionary side constraints
• Optimization, approximation, and complexity classes
• An approximation scheme for bin packing with conflicts
• The Maximum Flow Problem with Conflict and Forcing Conditions
• The Knapsack Problem with Conflict Graphs
• On the structure of all minimum cuts in a network and applications
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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