Parameterized Tractability of Multiway Cut with Parity Constraints

DOI10.1007/978-3-642-31594-7_63zbMath1272.68146OpenAlexW1533487312MaRDI QIDQ2843298

M. S. Ramanujan, Daniel Lokshtanov

Publication date: 12 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-31594-7_63

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (14)

Hitting Weighted Even Cycles in Planar Graphs ⋮ Linear Time Parameterized Algorithms for Subset Feedback Vertex Set ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ Hitting Selected (Odd) Cycles ⋮ Parameterized complexity of weighted multicut in trees ⋮ Parameterized complexity of multicut in weighted trees ⋮ Deletion to scattered graph classes. I: Case of finite number of graph classes ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ Backdoor Sets for CSP. ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ List H-coloring a graph by removing few vertices ⋮ Unnamed Item ⋮ Fixed-parameter tractability for subset feedback set problems with parity constraints

This page was built for publication: Parameterized Tractability of Multiway Cut with Parity Constraints