Parameterized algorithms for min-max multiway cut and list digraph homomorphism

DOI10.1016/j.jcss.2017.01.003zbMath1370.68131OpenAlexW2963096645MaRDI QIDQ2396830

Ignasi Sau, Christophe Paul, Eun Jung Kim, Dimitrios M. Thilikos

Publication date: 26 May 2017

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5573/

zbMATH Keywords

parameterized complexityfixed-parameter tractable algorithmmultiway cutdigraph homomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

A survey of parameterized algorithms and the complexity of edge modification ⋮ Reducing CMSO model checking to highly connected graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• List H-coloring a graph by removing few vertices
• The complexity of the list homomorphism problem for graphs
• Parameterized graph separation problems
• Efficient algorithms for counting parameterized list \(H\)-colorings
• Graphs of morphisms of graphs
• Approximating minimum feedback sets and multicuts in directed graphs
• An FPT 2-approximation for tree-cut decomposition
• List homomorphisms and circular arc graphs
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
• On Multiway Cut Parameterized above Lower Bounds
• Finding small separators in linear time via treewidth reduction
• Designing FPT Algorithms for Cut Problems Using Randomized Contractions
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Parallel Complexity of the Connected Subgraph Problem
• The Complexity of Multiterminal Cuts
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A simple min-cut algorithm
• Bi‐arc graphs and the complexity of list homomorphisms
• Multiway cuts in node weighted graphs
• Minimum bisection is fixed parameter tractable
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Space complexity of list H-colouring: a dichotomy
• Finding topological subgraphs is fixed-parameter tractable
• Algorithms – ESA 2004
• The Steiner k-Cut Problem
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Min-Max Graph Partitioning and Small Set Expansion
• The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable

This page was built for publication: Parameterized algorithms for min-max multiway cut and list digraph homomorphism