Important separators and parameterized algorithms

DOI10.1007/978-3-642-25870-1_2MaRDI QIDQ3104759zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Directed Subset Feedback Vertex Set is fixed-parameter tractable
• Parameterized tractability of multiway cut with parity constraints
• Directed subset feedback vertex set is fixed-parameter tractable
• Parameterized and Exact Computation
• Parameterized graph separation problems

Cites work

• \textsc{Multicut} is FPT
• 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
• Clustering with Local Restrictions
• Finding odd cycle transversals.
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Obtaining a bipartite graph by contracting few edges
• Parameterized graph separation problems
• The Complexity of Multiterminal Cuts

Cited in

(7)

• Excluding subdivisions of bounded degree graphs
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• scientific article; zbMATH DE number 4114676 (Why is no real title available?)
• Improved approximations for relative survivable network design
• Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
• Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
• All-subsets important separators with applications to sample sets, balanced separators and vertex sparsifiers in directed graphs

This page was built for publication: Important separators and parameterized algorithms

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