Prim-based support-graph preconditioners for min-cost flow problems

DOI10.1007/s10589-006-9005-9zbMath1148.90304OpenAlexW1988045438WikidataQ118165497 ScholiaQ118165497MaRDI QIDQ2643617

Claudio Gentile, Antonio Frangioni

Publication date: 27 August 2007

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/11568/109113

zbMATH Keywords

Prim algorithmInterior point algorithmsMin-cost flow problemsPreconditioned conjugated gradient method

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Interior-point methods (90C51) Deterministic network models in operations research (90B10)

Related Items

Computational evaluation of multi-iterative approaches for solving graph-structured large linear systems, Interior point methods 25 years later, Accelerated multigrid for graph Laplacian operators, Improving an interior-point approach for large block-angular problems by hybrid preconditioners

Uses Software

• PDNET
• IPM
• MCFClass

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A study of preconditioners for network interior point methods
• Triangulated graphs and the elimination process
• Spectral Analysis of (Sequences of) Graph Matrices
• A Computational Study of Cost Reoptimization for Min-Cost Flow Problems
• An Implementation of the Dual Affine Scaling Algorithm for Minimum-Cost Flow on Bipartite Uncapacitated Networks
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Block Sparse Cholesky Algorithms on Advanced Uniprocessor Computers
• A Bundle Type Dual-Ascent Approach to Linear Multicommodity Min-Cost Flow Problems
• A Specialized Interior-Point Algorithm for Multicommodity Network Flows
• New Preconditioners for KKT Systems of Network Flow Problems
• Experiments with a hybrid interior point/combinatorial approach for network flow problems
• Bundle-based relaxation methods for multicommodity capacitated fixed charge network design
• Complexity classification of some edge modification problems