Multicuts in unweighted digraphs with bounded degree and bounded tree-width

MaRDI QIDQ2741506zbMATH OpenFDO

Authors Gruia Calinescu, Cristina G. Fernandes

Publication date 24 October 2001

zbMATH Keywords

digraphdirected multicuttree-width

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• scientific article; zbMATH DE number 1187148
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs
• On the hardness of finding near-optimal multicuts in directed acyclic graphs
• New results on planar and directed multicuts

Cited in

(6)

• scientific article; zbMATH DE number 1187148 (Why is no real title available?)
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• Global and fixed-terminal cuts in digraphs
• Edge multiway cut and node multiway cut are hard for planar subcubic graphs
• On the hardness of finding near-optimal multicuts in directed acyclic graphs
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs

This page was built for publication: Multicuts in unweighted digraphs with bounded degree and bounded tree-width

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