scientific article; zbMATH DE number 2079369

zbMATH Open1092.68627MaRDI QIDQ4471328FDOQ4471328

Authors: Anupam Gupta 

Publication date: 28 July 2004

Title of this publication is not available (Why is that?)

Recommendations

• Approximation and Online Algorithms
• Approximating directed multicuts
• Greedy approximation algorithms for directed multicuts
• Approximation Algorithms for Steiner and Directed Multicuts
• Hardness of cut problems in directed graphs

zbMATH Keywords

minimum directed multicut problem

Mathematics Subject Classification ID

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

Cited In (20)

• Approximation and Online Algorithms
• A lower bound on the integrality gap for minimum multicut in directed networks
• Approximation and kernelization for chordal vertex deletion
• Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth
• On the Max-flow min-cut ratio for directed multicommodity flows
• On the complexity of the multicut problem in bounded tree-width graphs and digraphs
• Approximating multicut and the demand graph
• Multicommodity flows and cuts in polymatroidal networks
• The multi-multiway cut problem
• Greedy approximation algorithms for directed multicuts
• On the advantage of overlapping clusters for minimizing conductance
• A 2-approximation algorithm for the directed multiway cut problem
• A polynomial kernel for distance-hereditary vertex deletion
• An \(O(\sqrt n)\)-approximation algorithm for directed sparsest cut
• Beating the 2-approximation factor for global bicut
• Register loading via linear programming
• \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
• The checkpoint problem
• Enabling cuts on multiresolution representation
• Approximating directed multicuts

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 Q4471328)