Important Separators and Parameterized Algorithms

DOI10.1007/978-3-642-25870-1_2zbMath1341.05212OpenAlexW1559021984MaRDI QIDQ3104759

Dániel Marx

Publication date: 16 December 2011

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-25870-1_2

zbMATH Keywords

cutting of a graphmultyway cut problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (2)

Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Excluding subdivisions of bounded degree graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Parameterized graph separation problems
• Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
• On Multiway Cut Parameterized above Lower Bounds
• Clustering with Local Restrictions
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Algorithms for Multiterminal Cuts
• An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
• The Complexity of Multiterminal Cuts
• Multicut is FPT
• Fixed-parameter tractability of multicut parameterized by the size of the cutset

This page was built for publication: Important Separators and Parameterized Algorithms