Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow
From MaRDI portal
Publication:5874526
DOI10.4230/LIPICS.ESA.2020.55OpenAlexW3081626558MaRDI QIDQ5874526FDOQ5874526
Authors: Naveen Garg, N. Kumar 
Publication date: 7 February 2023
Full work available at URL: https://arxiv.org/abs/2007.14156
Recommendations
- Half-integral vertex covers on bipartite bidirected graphs: total dual integrality and cut-rank
- Approximate max-integral-flow/min-multicut theorems
- The complementary class of generalized flow cover inequalities
- A measure-theoretical max-flow-min-cut problem
- Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity
- Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs
- Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
- Tight spans of distances and the dual fractionality of undirected multiflow problems
- Primal-dual approximation algorithms for integral flow and multicut in trees
- scientific article; zbMATH DE number 1099084
Cites Work
- A General Approximation Technique for Constrained Forest Problems
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Excluded minors, network decomposition, and multicommodity flow
- A primal-dual approximation algorithm for generalized Steiner network problems
- Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
Cited In (2)
This page was built for publication: Dual Half-Integrality for Uncrossable Cut Cover and Its Application to Maximum Half-Integral Flow
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874526)
