Complexity of minimum irreducible infeasible subsystem covers for flow networks
From MaRDI portal
Publication:1752598
DOI10.1016/j.dam.2018.02.025zbMath1387.05243OpenAlexW2793983615MaRDI QIDQ1752598
Marc E. Pfetsch, Imke Joormann
Publication date: 24 May 2018
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2018.02.025
Analysis of algorithms and problem complexity (68Q25) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Flows in graphs (05C21)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A theorem on flows in networks
- On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
- The facets of the polyhedral set determined by the Gale-Hoffman inequalities
- Some results concerning post-infeasibility analysis
- The complexity and approximability of finding maximum feasible subsystems of linear relations
- How to compute least infeasible flows
- Consistency, redundancy, and implied equalities in linear systems
- Finding the minimum weight IIS cover of an infeasible system of linear inequalities
- An effective polynomial-time heuristic for the minimum-cardinality IIS set-covering problem
- A note on resolving infeasibility in linear programs by constraint relaxation
- The minimum shift design problem
- Feasibility and infeasibility in optimization. Algorithms and computational methods.
- Fast Heuristics for the Maximum Feasible Subsystem Problem
- Evaluating Gas Network Capacities
- Diagnosing Infeasibility in Min-cost Network Flow Problems Part II: Primal Infeasibility
- Easy problems for tree-decomposable graphs
- Branch-and-Cut for the Maximum Feasible Subsystem Problem
- Diagnosing Infeasibility in Min-cast Network Flow Problems Part I: Dual Infeasibility
- Identifying Minimally Infeasible Subsystems of Inequalities
- A search strategy for the elementary cycles of a directed graph
- On Algorithms for Enumerating All Circuits of a Graph
- A characterization of irreducible infeasible subsystems in flow networks
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
