Maximum reachability preserved graph cut

DOI10.1016/J.TCS.2020.08.016MaRDI QIDQ2202008zbMATH OpenOpenAlexFDO

Authors Dongjing Miao, Jianzhong Li, Zhipeng Cai

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 analysishardnessmultiway cutreachability-preserved cut

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the connectivity preserving minimum cut problem
• Approximation and hardness results for label cut and related problems
• Approximation and Hardness Results for Label Cut and Related Problems
• Efficient Algorithms for the Label Cut Problems
• Labeled cuts in graphs

Cites work

• A simplified NP-complete satisfiability problem
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Removing undesirable flows by edge deletion
• Sufficient conditions for reachability in automata networks with priorities
• Vertex cover in conflict graphs

Cited in

(3)

• Delta invariant for Eulerian digraphs
• On the hardness of Reachability Reduction
• A sub-linear time algorithm for approximating k-nearest-neighbor with full quality guarantee

This page was built for publication: Maximum reachability preserved graph cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2202008)