Parameterized algorithms for min-max multiway cut and list digraph homomorphism
From MaRDI portal
Publication:2396830
DOI10.1016/J.JCSS.2017.01.003zbMATH Open1370.68131OpenAlexW2963096645MaRDI QIDQ2396830FDOQ2396830
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/
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
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
- On multiway cut parameterized above lower bounds
- The Complexity of Multiterminal Cuts
- Multiway cuts in node weighted graphs
- Parameterized graph separation problems
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Rounding algorithms for a geometric embedding of minimum multiway cut
- Finding small separators in linear time via treewidth reduction
- Title not available (Why is that?)
- Parallel Complexity of the Connected Subgraph Problem
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- The minimum \(k\)-way cut of bounded size is fixed-parameter tractable
- Approximating minimum feedback sets and multicuts in directed graphs
- Finding topological subgraphs is fixed-parameter tractable
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- List homomorphisms and circular arc graphs
- A simple min-cut algorithm
- The complexity of the list homomorphism problem for graphs
- Bi‐arc graphs and the complexity of list homomorphisms
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- The dichotomy of list homomorphisms for digraphs
- Efficient algorithms for counting parameterized list \(H\)-colorings
- Minimum bisection is fixed parameter tractable
- Designing FPT algorithms for cut problems using randomized contractions
- List H-coloring a graph by removing few vertices
- Title not available (Why is that?)
- Graphs of morphisms of graphs
- The Steiner k-Cut Problem
- Title not available (Why is that?)
- Algorithms – ESA 2004
- Min-Max Graph Partitioning and Small Set Expansion
- An FPT 2-approximation for tree-cut decomposition
- Space complexity of list H-colouring: a dichotomy
Cited In (3)
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)
