Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs
DOI10.1007/S10107-015-0944-8zbMATH Open1328.90131OpenAlexW2132147722MaRDI QIDQ896272FDOQ896272
Authors: Hassene Aissi, S. Thomas McCormick, Maurice Queyranne, A. R. Mahjoub 
Publication date: 9 December 2015
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-015-0944-8
Recommendations
Multi-objective and goal programming (90C29) Graph algorithms (graph-theoretic aspects) (05C85) Sensitivity, stability, parametric optimization (90C31) Connectivity (05C40)
Cites Work
- A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
- Multicriteria Optimization
- Algorithmic Aspects of Graph Connectivity
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
- Minimizing symmetric submodular functions
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- Complexity of some parametric integer and network programming problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- A new approach to the minimum cut problem
- Computing All Small Cuts in an Undirected Network
- The upper bound theorem for polytopes: An easy proof of its asymptotic version
- Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases
- A simple min-cut algorithm
- Title not available (Why is that?)
- Multicriteria global minimum cuts
- Minimum cuts in near-linear time
- Output-sensitive results on convex hulls, extreme points, and related problems
- Parametric multiple sequence alignment and phylogeny construction
- A fast hypergraph min-cut algorithm for circuit partitioning
- Cutsets and partitions of hypergraphs
- Lower Bounds in a Parallel Model without Bit Operations
- Modeling hypergraphs by graphs with the same mincut properties
- On the number of small cut in a graph
- Sketching cuts in graphs and hypergraphs
- Slicing Space
- A near-linear time algorithm for constructing a cactus representation of minimum cuts
- Suboptimal cuts: their enumeration, weight and number (extended abstract)
- A Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cuts
Cited In (15)
- Complexity of source-sink monotone 2-parameter min cut
- Faster algorithms for next breakpoint and max value for parametric global minimum cuts
- Minimum cuts and sparsification in hypergraphs
- Parametric computation of minimum-cost flows with piecewise quadratic costs
- Multicriteria global minimum cuts
- Deterministic enumeration of all minimum cut-sets and \(k\)-cut-sets in hypergraphs for fixed \(k\)
- Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs.
- A Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cuts
- Approximating multiobjective optimization problems: how exact can you be?
- Maximum flows in parametric graph templates
- Multicriteria cuts and size-constrained \(k\)-cuts in hypergraphs
- Algorithms and Computation
- An approximation algorithm for a general class of multi-parametric optimization problems
- Enumerating parametric global minimum cuts by random interleaving
- Multi-objective unconstrained combinatorial optimization: a polynomial bound on the number of extreme supported solutions
This page was built for publication: Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896272)
