A Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cuts

DOI10.1007/978-3-319-07557-0_3MaRDI QIDQ5418982zbMATH OpenOpenAlexFDO

Authors Hassene Aissi, S. Thomas McCormick, Maurice Queyranne, A. R. Mahjoub

Publication date 2 June 2014

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-07557-0_3

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Multi-objective and goal programming (90C29) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs
• Deterministic global minimum cut of a simple graph in near-linear time
• Algorithms and Computation
• Multicriteria global minimum cuts
• A Strongly Polynomial Cut Canceling Algorithm for Minimum Cost Submodular Flow
• A fast algorithm for the generalized parametric minimum cut problem and applications
• A polynomial-time approximation scheme for planar multiway cut
• Approximation algorithms for feasible cut and multicut problems
• An improved parameterized algorithm for the multicut problem
• Structural and algorithmic properties for parametric minimum cuts

Cited in

(7)

• Multicriteria global minimum cuts
• Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems
• Faster algorithms for next breakpoint and max value for parametric global minimum cuts
• Enumerating parametric global minimum cuts by random interleaving
• Algorithms and Computation
• Strongly polynomial-time approximation for a class of bicriteria problems.
• Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs

This page was built for publication: A Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cuts

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