Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs
From MaRDI portal
Publication:896272
DOI10.1007/s10107-015-0944-8zbMath1328.90131OpenAlexW2132147722MaRDI QIDQ896272
Hassene Aissi, S. Thomas McCormick, Maurice Queyranne, Ali Ridha 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
Multi-objective and goal programming (90C29) Sensitivity, stability, parametric optimization (90C31) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items
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, Complexity of source-sink monotone 2-parameter min cut, Maximum flows in parametric graph templates, Multi-objective unconstrained combinatorial optimization: a polynomial bound on the number of extreme supported solutions, Multicriteria cuts and size-constrained \(k\)-cuts in hypergraphs, Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs., An approximation algorithm for a general class of multi-parametric optimization problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parametric multiple sequence alignment and phylogeny construction
- Modeling hypergraphs by graphs with the same mincut properties
- Minimizing symmetric submodular functions
- Output-sensitive results on convex hulls, extreme points, and related problems
- On the number of small cut in a graph
- The upper bound theorem for polytopes: An easy proof of its asymptotic version
- Multicriteria global minimum cuts
- A fast hypergraph min-cut algorithm for circuit partitioning
- Sketching Cuts in Graphs and Hypergraphs
- Algorithmic Aspects of Graph Connectivity
- Complexity of some parametric integer and network programming problems
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases
- Lower Bounds in a Parallel Model without Bit Operations
- A new approach to the minimum cut problem
- Computing All Small Cuts in an Undirected Network
- A simple min-cut algorithm
- Slicing Space
- Suboptimal cuts: Their enumeration, weight and number
- Multicriteria Optimization
- A Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cuts
- Minimum cuts in near-linear time
- Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
- A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
- Cutsets and partitions of hypergraphs
