Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts

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

zbMATH Keywords

parametric optimizationglobal minimum cut

Mathematics Subject Classification ID

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