A new contraction technique with applications to congruency-constrained cuts
From MaRDI portal
Publication:5918921
DOI10.1007/s10107-020-01498-xzbMath1450.90046OpenAlexW2942644636WikidataQ114228501 ScholiaQ114228501MaRDI QIDQ5918921
Publication date: 28 August 2020
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/20.500.11850/412160
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Combinatorial optimization (90C27) Graph theory (05C99)
Related Items (3)
Hitting Weighted Even Cycles in Planar Graphs ⋮ Advances on strictly \(\varDelta \)-modular IPs ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
- A construction for binary matroids
- The parsimonious property of cut covering problems and its applications
- On the minors of an incidence matrix and Smith normal form
- Minimizing submodular functions over families of sets
- A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs
- Submodular minimization under congruency constraints
- Geometric random edge
- Efficient splitting off algorithms for graphs
- Randomized Rounding for the Largest Simplex Problem
- Solving the stable set problem in terms of the odd cycle packing number
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- Multi-Terminal Network Flows
- Combinatorial Optimization with Rational Objective Functions
- Odd Minimum Cut-Sets and b-Matchings
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- On some connectivity properties of Eulerian graphs
- A Reduction Method for Edge-Connectivity in Graphs
- A new approach to the minimum cut problem
- A strongly polynomial algorithm for bimodular integer linear programming
- On largest volume simplices and sub-determinants
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Efficient Edge Splitting-Off Algorithms Maintaining All-Pairs Edge-Connectivities
- Combinatorial optimization. Theory and algorithms
This page was built for publication: A new contraction technique with applications to congruency-constrained cuts