The Complexity of Multiterminal Cuts
From MaRDI portal
Publication:4305362
DOI10.1137/S0097539792225297zbMath0809.68075WikidataQ56077927 ScholiaQ56077927MaRDI QIDQ4305362
Mihalis Yannakakis, Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, P. D. Seymour
Publication date: 17 October 1994
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10)
Related Items
On Multiway Cut Parameterized above Lower Bounds, The partition problem, A logical approach to multicut problems, FPT Suspects and Tough Customers: Open Problems of Downey and Fellows, A Faster Parameterized Algorithm for Group Feedback Edge Set, List coloring in the absence of two subgraphs, On the connectivity preserving minimum cut problem, Separation of partition inequalities with terminals, One more well-solved case of the multifacility location problem, Supermodular functions and the complexity of MAX CSP, Covering Vectors by Spaces: Regular Matroids, The maximum integer multiterminal flow problem in directed graphs, An improved parameterized algorithm for the minimum node multiway cut problem, Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems, Parameterized algorithms for min-max multiway cut and list digraph homomorphism, Identifying Codes in Line Graphs, Global and fixed-terminal cuts in digraphs, Multicuts in planar and bounded-genus graphs with bounded number of terminals, Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem, Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability, The single allocation problem in the interacting three-hub network, Clique Cover and Graph Separation, The Complexity of Approximately Counting Tree Homomorphisms, Mean isoperimetry with control on outliers: exact and approximation algorithms, Approximation and Kernelization for Chordal Vertex Deletion, Submodular reassignment problem for reallocating agents to tasks with synergy effects, An approximation algorithm for maxk-uncut with capacity constraints, The vertex \(k\)-cut problem, Algorithms for Multiterminal Cuts, Performing Multicut on Walkable Environments, Unnamed Item, Eulerian walks in temporal graphs, Multicut Is FPT, On the generalized multiway cut in trees problem, An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem, The Complexity of Valued CSPs, Minimum Violation Vertex Maps and Their Applications to Cut Problems, Approximation Algorithms for CSPs, On the complexity of the selective graph coloring problem in some special classes of graphs, Multiway cuts in directed and node weighted graphs, Cut problems in graphs with a budget constraint, The complexity of soft constraint satisfaction, Odd Multiway Cut in Directed Acyclic Graphs, Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs, A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals, Steiner diagrams and \(k\)-star hubs, Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions, How to Cut a Graph into Many Pieces, The Complexity and Approximability of Minimum Contamination Problems, Mixed-Integer Programming for Cycle Detection in Nonreversible Markov Processes, Submodular Cost Allocation Problem and Applications, A new?old algorithm for minimum-cut and maximum-flow in closure graphs, Unnamed Item, Optimal 3-terminal cuts and linear programming, A sufficiently fast algorithm for finding close to optimal clique trees, Fixed-Parameter Algorithms for Finding Agreement Supertrees, Some formulations for the group Steiner tree problem, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Correlation clustering in general weighted graphs, Generalized \(k\)-multiway cut problems, Capacitated partial inverse maximum spanning tree under the weighted Hamming distance, Exact algorithms for a discrete metric labeling problem, A Lagrangian Relaxation-Based Heuristic to Solve Large Extended Graph Partitioning Problems, Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth, Approximation Algorithms for k-Hurdle Problems, Fixed parameter approximation scheme for min-max \(k\)-cut, A simple algorithm for the multiway cut problem, The Monotone Satisfiability Problem with Bounded Variable Appearances, Improving the integrality gap for multiway cut, Lower bounds for the happy coloring problems, Fixed parameter approximation scheme for min-max \(k\)-cut, Weakly Modular Graphs and Nonpositive Curvature, Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width, Exact algorithms for a discrete metric labeling problem, Finding a Small Number of Colourful Components, Quick separation in chordal and split graphs, Beating the 2-approximation factor for global bicut, Unnamed Item, Simplex Transformations and the Multiway Cut Problem, Important Separators and Parameterized Algorithms, A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract), 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, New results on planar and directed multicuts, On Computing the Maximum Parsimony Score of a Phylogenetic Network, Unnamed Item, Unnamed Item, ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS, Fixed-parameter tractability for subset feedback set problems with parity constraints, The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects, Multiway cut and integer flow problems in trees, Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time, Complexity dichotomy for oriented homomorphism of planar graphs with large girth, On Lipschitz extension from finite subsets, Extended cuts, On the minimum and maximum selective graph coloring problems in some graph classes, Parameterized graph separation problems, Some constrained partitioning problems and majorization, A graph theoretical approach to the firebreak locating problem, Solving \((k-1)\)-stable instances of \texttt{k-terminal cut} with isolating cuts, CPG graphs: some structural and hardness results, The multi-terminal vertex separator problem: branch-and-cut-and-price, On weighted multiway cuts in trees, On the (near) optimality of extended formulations for multi-way cut in social networks, On approximating the memory-constrained module allocation problem, Experimental evaluation of a local search approximation algorithm for the multiway cut problem, A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut, Parameterized complexity dichotomy for \textsc{Steiner Multicut}, On generalized greedy splitting algorithms for multiway partition problems, Hard cases of the multifacility location problem, Complexity of metric dimension on planar graphs, Approximation algorithms for requirement cut on graphs, Roman domination in subgraphs of grids, A new approach for the multiobjective minimum spanning tree, Partial multicuts in trees, \(\ell_p\)-norm multiway cut, Complexity of paired domination in AT-free and planar graphs, A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms, Towards duality of multicommodity multiroute cuts and flows: multilevel ball-growing, Algorithms for shortest paths and \(d\)-cycle problems, The planar multiterminal cut problem, The multi-multiway cut problem, Placing quantified variants of 3-SAT and \textsc{not-all-equal} 3-SAT in the polynomial hierarchy, The complexity of multicut and mixed multicut problems in (di)graphs, Partitioning sparse graphs into an independent set and a graph with bounded size components, A golden ratio parameterized algorithm for cluster editing, Fast approximate energy minimization with label costs, Improved parameterized and exact algorithms for cut problems on trees, Two-stage robust network design with exponential scenarios, On integer and bilevel formulations for the \(k\)-vertex cut problem, Approximation algorithms for \(k\)-hurdle problems, Hardness of approximation for crossing number, An approximation algorithm for the generalized \(k\)-multicut problem, Community detection with the weighted parsimony criterion, The convexity of induced paths of order three and applications: complexity aspects, Computing minimum cuts by randomized search heuristics, Partial inverse maximum spanning tree in which weight can only be decreased under \(l_p\)-norm, A tight \(\sqrt{2} \)-approximation for linear 3-cut, Models and methods for solving the problem of network vulnerability, Geometric multicut: shortest fences for separating groups of objects in the plane, Generating partitions of a graph into a fixed number of minimum weight cuts, Restricted vertex multicut on permutation graphs, Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs, Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs, Reducing the domination number of graphs via edge contractions and vertex deletions, Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity, Polyhedral study of the connected subgraph problem, Generating cut conjunctions in graphs and related problems, The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut, Finding the closest ultrametric, Compact samples for data dissemination, Inapproximability of the Tutte polynomial, On the complexity of the multicut problem in bounded tree-width graphs and digraphs, Algorithmic aspects of homophyly of networks, Fixed-parameter algorithms for DAG partitioning, Primal-dual approximation algorithms for integral flow and multicut in trees, Analysis of budget for interdiction on multicommodity network flows, The critical node detection problem in networks: a survey, Improved approximation algorithms for the maximum happy vertices and edges problems, L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem, Path-disruption games: bribery and a probabilistic model, An FPT algorithm for planar multicuts with sources and sinks on the outer face, Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem, Discrete and continuous models for partitioning problems, Parameterized complexity of the spanning tree congestion problem, Disjoint paths in sparse graphs, Optimal cuts in graphs and statistical mechanics, Greedy splitting algorithms for approximating multiway partition problems, Minimal multicut and maximal integer multiflow: a survey, The multi-terminal maximum-flow network-interdiction problem, Complexity and characterization aspects of edge-related domination for graphs, Simple and improved parameterized algorithms for multiterminal cuts, On the hardness of finding near-optimal multicuts in directed acyclic graphs, An improved approximation algorithm for requirement cut, Revisiting a simple algorithm for the planar multiterminal cut problem, Eisenberg-Gale markets: algorithms and game-theoretic properties, Inequity aversion pricing over social networks: approximation algorithms and hardness results, Minimum 0-extension problems on directed metrics, Evolutionary trees: An integer multicommodity max-flow -- min-cut theorem, Color-texture segmentation using unsupervised graph cuts, Cardinality constrained and multicriteria (multi)cut problems, Minimum multiway cuts in trees, A simple algorithm for multicuts in planar graphs with outer terminals, An improved approximation algorithm of MULTIWAY CUT., Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem, Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties, Metrics with finite sets of primitive extensions, A characterization of minimizable metrics in the multifacility location problem, On embedding complete graphs into hypercubes, Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems, Political districting to minimize cut edges, Königsberg sightseeing: Eulerian walks in temporal graphs, Parameterized complexity of the anchored \(k\)-core problem for directed graphs, A greedy algorithm for multicut and integral multiflow in rooted trees, Parameterized complexity of weighted multicut in trees, Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree, Parameterized complexity of multicut in weighted trees, Establishing herd immunity is hard even in simple geometric networks, Structural parameterization of cluster deletion, Two‐stage stochastic minimum s − t cut problems: Formulations, complexity and decomposition algorithms, Better hardness results for the minimum spanning tree congestion problem, Approximation algorithms for feasible cut and multicut problems, Target set selection with maximum activation time, A constant-ratio approximation algorithm for a class of hub-and-spoke network design problems and metric labeling problems: star metric case, Approximating maximum integral multiflows on bounded genus graphs, A survey of parameterized algorithms and the complexity of edge modification, Fun with replicas: tripartitions in tensor networks and gravity, A local search approximation algorithm for the multiway cut problem, The \textsc{Red-Blue Separation} problem on graphs, Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles, Algorithmic and complexity aspects of problems related to total restrained domination for graphs, Approximating Requirement Cut via a Configuration LP, Steiner trees and polyhedra, On interval representations of graphs, Discrete convexity and polynomial solvability in minimum 0-extension problems, Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
