The complexity of multicut and mixed multicut problems in (di)graphs

DOI10.1016/J.TCS.2013.10.022zbMath1352.05173OpenAlexW2027659362MaRDI QIDQ391767

Anders Yeo, Jörgen Bang-Jensen

Publication date: 13 January 2014

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

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

zbMATH Keywords

mixed problemNP-completedichotomymixed graphsfeedback arc setmulticut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (1)

Acyclic Digraphs

Cites Work

• Unnamed Item
• Minimal multicut and maximal integer multiflow: a survey
• The Complexity of Multiterminal Cuts
• Multiway cuts in directed and node weighted graphs
• Multicut is FPT
• Digraphs
• Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs

This page was built for publication: The complexity of multicut and mixed multicut problems in (di)graphs