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

DOI10.1016/J.JCSS.2017.01.003MaRDI QIDQ2396830zbMATH OpenOpenAlexFDO

Authors Eun Jung Kim, Christophe Paul, Ignasi Sau, 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

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

Recommendations

• Parameterized algorithms for MIN-MAX multiway cut and List digraph homomorphism
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
• An improved parameterized algorithm for the minimum node multiway cut problem

Cites work

• scientific article; zbMATH DE number 5485537 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1834657 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 2119718 (Why is no real title available?)
• A simple min-cut algorithm
• Algorithms – ESA 2004
• Approximating minimum feedback sets and multicuts in directed graphs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Bi‐arc graphs and the complexity of list homomorphisms
• Designing FPT algorithms for cut problems using randomized contractions
• Efficient algorithms for counting parameterized list H-colorings
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Finding small separators in linear time via treewidth reduction
• Finding topological subgraphs is fixed-parameter tractable
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• Graphs of morphisms of graphs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• List homomorphisms and circular arc graphs
• Min-Max Graph Partitioning and Small Set Expansion
• Minimum bisection is fixed parameter tractable
• Multiway cuts in node weighted graphs
• Parallel Complexity of the Connected Subgraph Problem
• Parameterized graph separation problems
• Space complexity of list H-colouring: a dichotomy
• The Complexity of Multiterminal Cuts
• The Steiner k-Cut Problem
• The complexity of the list homomorphism problem for graphs
• The dichotomy of list homomorphisms for digraphs
• The minimum \(k\)-way cut of bounded size is fixed-parameter tractable

Cited in

(3)

• Parameterized algorithms for MIN-MAX multiway cut and List digraph homomorphism
• A survey of parameterized algorithms and the complexity of edge modification
• Reducing CMSO model checking to highly connected graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2396830)