An algorithm for computing maximum solution bases

DOI10.1016/0167-6377(90)90025-ZMaRDI QIDQ2641220zbMATH OpenOpenAlexFDO

Authors Refael Hassin

Publication date 1990

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(90)90025-z

zbMATH Keywords

maximum solution basismultiterminal cut problem

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Review text

The paper is concerned with families of problems defined on a common solution space, each problem having its own subset of feasible solutions. Each problem is associated with a cost and the value of a problem is the minimum cost of a feasible solution. A key concept in this approach is the maximum solution basis, which, roughly speaking is a subset of problems with the following property: finding the values of the problems in the maximum solution basis allows to compute easily the value of any of the problems. An algorithm for generating a maximum solution basis is described. The possibilities of applying this algorithm to the multiterminal cut problem are discussed.

Recommendations

• Solution Bases of Multiterminal Cut Problems
• scientific article; zbMATH DE number 176254
• Multiterminal xcut problems
• Algorithms for Multiterminal Cuts
• Minimum cut bases in undirected networks

Cites work

• A Theory on Extending Algorithms for Parametric Problems
• Ancestor tree for arbitrary multi-terminal cut functions
• scientific article; zbMATH DE number 432789 (Why is no real title available?)
• Maximum concurrent flows and minimum cuts
• Multi-terminal maximum flows in node-capacitated networks
• Multi-Terminal Network Flows
• Multiterminal xcut problems
• Solution Bases of Multiterminal Cut Problems
• Very Simple Methods for All Pairs Network Flow Analysis

Cited in

(3)

• Multiterminal xcut problems
• Solution Bases of Multiterminal Cut Problems
• Flow trees for vertex-capacitated networks

This page was built for publication: An algorithm for computing maximum solution bases

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