Maximum reachability preserved graph cut

DOI10.1016/j.tcs.2020.08.016zbMath1455.68145MaRDI QIDQ2202008

Zhipeng Cai, Dongjing Miao, Jian-Zhong Li

Publication date: 17 September 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.08.016

zbMATH Keywords

complexity analysis; hardness; multiway cut; reachability-preserved cut

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

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

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