Parameterized algorithms for min-max multiway cut and list digraph homomorphism
type: Item
instance of: scholarly article
title: Parameterized algorithms for min-max multiway cut and list digraph homomorphism
zbMATH Open document ID: 1370.68131
author: Eun Jung Kim
author: Christophe Paul
author: Ignasi Sau
author: Dimitrios M. Thilikos
published in: Journal of Computer and System Sciences
publication date: 2017-05-26T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5573/
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6723278
zbMATH Keywords: parameterized complexity
zbMATH Keywords: fixed-parameter tractable algorithm
zbMATH Keywords: multiway cut
zbMATH Keywords: digraph homomorphism
MaRDI profile type: Publication
OpenAlex ID: W2963096645
cites work: Min-Max Graph Partitioning and Small Set Expansion
cites work: Graphs of morphisms of graphs
cites work: The Steiner k-Cut Problem
cites work: Designing FPT Algorithms for Cut Problems Using Randomized Contractions
cites work: List H-coloring a graph by removing few vertices
cites work: Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
cites work: Minimum bisection is fixed parameter tractable
cites work: On Multiway Cut Parameterized above Lower Bounds
cites work: The Complexity of Multiterminal Cuts
cites work: Efficient algorithms for counting parameterized list \(H\)-colorings
cites work: Q4779153
cites work: Algorithms – ESA 2004
cites work: Space complexity of list H-colouring: a dichotomy
cites work: The complexity of the list homomorphism problem for graphs
cites work: Approximating minimum feedback sets and multicuts in directed graphs
cites work: List homomorphisms and circular arc graphs
cites work: Bi‐arc graphs and the complexity of list homomorphisms
cites work: Q4198056
cites work: Multiway cuts in node weighted graphs
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Finding topological subgraphs is fixed-parameter tractable
cites work: Finding a Maximum Cut of a Planar Graph in Polynomial Time
cites work: Q4828516
cites work: Q5365149
cites work: The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable
cites work: Rounding algorithms for a geometric embedding of minimum multiway cut
cites work: An FPT 2-approximation for tree-cut decomposition
cites work: Parallel Complexity of the Connected Subgraph Problem
cites work: Parameterized graph separation problems
cites work: Finding small separators in linear time via treewidth reduction
cites work: Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
cites work: Q3549709
cites work: Q4828991
cites work: A simple min-cut algorithm
cites work: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
DOI: 10.1016/J.JCSS.2017.01.003
description: scientific article