scientific article; zbMATH DE number 1187148

MaRDI QIDQ3840353zbMATH OpenFDO

Authors Gruia Calinescu, Cristina G. Fernandes, Bruce Reed

Publication date 8 April 1999

zbMATH Keywords

hardness resultsmulticut problempolynomial time approximation schemeunweighted graphs

Mathematics Subject Classification ID

Integer programming (90C10) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Multicuts in unweighted digraphs with bounded degree and bounded tree-width
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs
• Multicut on graphs of bounded clique-width
• Multi-multiway cut problem on graphs of bounded branch width
• Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
• Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
• scientific article; zbMATH DE number 1875430
• On weighted multiway cuts in trees
• Multiway cuts in node weighted graphs

Cited in

(9)

• Models and methods for solving the problem of network vulnerability
• Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
• Multicuts in unweighted digraphs with bounded degree and bounded tree-width
• From Graph Orientation to the Unweighted Maximum Cut
• Performing Multicut on Walkable Environments
• Multicut on graphs of bounded clique-width
• Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
• Multi-multiway cut problem on graphs of bounded branch width
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs

This page was built for publication:

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