Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts
From MaRDI portal
Publication:5041732
DOI10.1007/978-3-030-45771-6_3zbMath1503.90139arXiv1911.11847OpenAlexW3017282729MaRDI QIDQ5041732
Maurice Queyranne, Hassene Aissi, S. Thomas McCormick
Publication date: 14 October 2022
Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1911.11847
Programming involving graphs or networks (90C35) Sensitivity, stability, parametric optimization (90C31)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A deterministic view of random sampling and its use in geometry
- Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs
- The upper envelope of piecewise linear functions: Algorithms and applications
- Algorithms and complexity analysis for some flow problems
- New applications of random sampling in computational geometry
- Handbook of Approximation Algorithms and Metaheuristics
- Algorithmic Aspects of Graph Connectivity
- Complexity of some parametric integer and network programming problems
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Linear Programming in Linear Time When the Dimension Is Fixed
- Combinatorial Optimization with Rational Objective Functions
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- 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
- Minimax parametric optimization problems and multi-dimensional parametric searching
- Enumerating parametric global minimum cuts by random interleaving
- Minimum cuts in near-linear time