Global and fixed-terminal cuts in digraphs

DOI10.4230/LIPIcs.APPROX-RANDOM.2017.2zbMath1467.68134arXiv1612.00156MaRDI QIDQ5002602

Chao Xu, Tamás Király, Euiwoong Lee, Kristóf Bérczi, Karthekeyan Chandrasekaran

Publication date: 28 July 2021

Full work available at URL: https://arxiv.org/abs/1612.00156

zbMATH Keywords

directed graphs; hardness of approximation; arborescence; graph cuts

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

05C20: Directed graphs (digraphs), tournaments