Odd Multiway Cut in Directed Acyclic Graphs

DOI10.4230/LIPIcs.IPEC.2017.12zbMath1443.68124arXiv1708.02323OpenAlexW2962809577MaRDI QIDQ5111871

Karthekeyan Chandrasekaran, Sahand Mozaffari

Publication date: 27 May 2020

Full work available at URL: https://arxiv.org/abs/1708.02323

zbMATH Keywords

approximation algorithmsfixed-parameter tractabilityodd multiway cut

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

Unnamed Item

Cites Work

• Packing non-zero \(A\)-paths in group-labelled graphs
• Geometric algorithms and combinatorial optimization
• Packing odd paths
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Parametrized complexity theory.
• Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Parameterized Tractability of Multiway Cut with Parity Constraints
• Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
• The even-path problem for graphs and digraphs
• Weak duality for packing edge-disjoint odd (u, v)-trails
• Faster Parameterized Algorithms Using Linear Programming
• Paths, Trees, and Flowers
• Parameterized Algorithms
• Maximum matching and a polyhedron with 0,1-vertices
• Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs

This page was built for publication: Odd Multiway Cut in Directed Acyclic Graphs