On finding the K best cuts in a network

DOI10.1016/0167-6377(84)90083-XMaRDI QIDQ792224zbMATH OpenOpenAlexFDO

Authors Horst W. Hamacher, Jean-Claude Picard, Maurice Queyranne

Publication date 1984

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

Full work available at URL https://doi.org/10.1016/0167-6377(84)90083-x

zbMATH Keywords

best cutscounterexampleflow algorithmranking of solutions

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Review text

A counterexample to an algorithm of the first author [ibid. 1, 186-189 (1982; Zbl 0505.90023)] for finding K best cuts in a network is given.

Cites work

• An O(K.n**4) algorithm for finding the K best cuts in a network
• scientific article; zbMATH DE number 3906193 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
• Some Network Flow Problems Solved with Pseudo-Boolean Programming

Cited in

(5)

• A note on \(K\) best network flows
• Approximating \(k\)-cuts using network strength as a Lagrangean relaxation
• The Kth TSP is pseudopolynomial when TSP is polynomial
• Mimicking Networks and Succinct Representations of Terminal Cuts
• A complexity map of probabilistic reasoning for neurosymbolic classification techniques

This page was built for publication: On finding the K best cuts in a network

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