Multiway cuts in node weighted graphs
From MaRDI portal
Publication:4819693
DOI10.1016/S0196-6774(03)00111-1zbMath1068.68178OpenAlexW2010004564MaRDI QIDQ4819693
Naveen Garg, Mihalis Yannakakis, Vijay V. Vazirani
Publication date: 4 October 2004
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0196-6774(03)00111-1
Related Items
Extended cuts ⋮ Parameterized graph separation problems ⋮ Faster exact algorithms for some terminal set problems ⋮ On Multiway Cut Parameterized above Lower Bounds ⋮ Approximation algorithms for treewidth ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Improving multicut in directed trees by upgrading nodes ⋮ Minimum failure explanations for path vector routing changes ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ Global and fixed-terminal cuts in digraphs ⋮ A heuristic method for the minimum toll booth problem ⋮ Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem ⋮ Clique Cover and Graph Separation ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ Vertex downgrading to minimize connectivity ⋮ The vertex \(k\)-cut problem ⋮ Algorithms for Multiterminal Cuts ⋮ Fission: Practical algorithms for computing minimum balanced node separators ⋮ On integer and bilevel formulations for the \(k\)-vertex cut problem ⋮ Approximation algorithms for \(k\)-hurdle problems ⋮ Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees ⋮ Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems ⋮ Unnamed Item ⋮ Fixed-parameter evolutionary algorithms and the vertex cover problem ⋮ A tight \(\sqrt{2} \)-approximation for linear 3-cut ⋮ Restricted vertex multicut on permutation graphs ⋮ An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem ⋮ Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity ⋮ Enumerating minimal subset feedback vertex sets ⋮ The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut ⋮ Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs ⋮ Register loading via linear programming ⋮ Multi-Budgeted Directed Cuts ⋮ How to Cut a Graph into Many Pieces ⋮ Submodular Cost Allocation Problem and Applications ⋮ A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs ⋮ Minimal multicut and maximal integer multiflow: a survey ⋮ Solution methods for the vertex variant of the network system vulnerability analysis problem ⋮ Simple and improved parameterized algorithms for multiterminal cuts ⋮ On the hardness of finding near-optimal multicuts in directed acyclic graphs ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ The maximum happy induced subgraph problem: bounds and algorithms ⋮ Inequity aversion pricing over social networks: approximation algorithms and hardness results ⋮ Discrete Convex Functions on Graphs and Their Algorithmic Applications ⋮ Computing minimum multiway cuts in hypergraphs ⋮ Approximation Algorithms for k-Hurdle Problems ⋮ A simple algorithm for the multiway cut problem ⋮ Faster graph bipartization ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ Subset feedback vertex set on graphs of bounded independent set size ⋮ Iterative Compression for Exactly Solving NP-Hard Minimization Problems ⋮ On the Approximability of Some Haplotyping Problems ⋮ A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs ⋮ A simple algorithm for multicuts in planar graphs with outer terminals ⋮ Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program ⋮ Recent results on approximating the Steiner tree problem and its generalizations ⋮ Simplex Transformations and the Multiway Cut Problem ⋮ The Multi-terminal Vertex Separator Problem: Polytope Characterization and TDI-ness ⋮ Approximation algorithms for vertex happiness ⋮ On a bidirected relaxation for the MULTIWAY CUT problem ⋮ On the parameterized complexity of separating certain sources from the target ⋮ Multi-budgeted directed cuts ⋮ New results on planar and directed multicuts ⋮ A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem ⋮ Node multiway cut and subset feedback vertex set on graphs of bounded mim-width ⋮ Multiway cut and integer flow problems in trees
