Linear kernels for separating a graph into components of bounded size

DOI10.1016/j.jcss.2017.04.004zbMath1371.05293arXiv1608.05816OpenAlexW2515668856MaRDI QIDQ2361357

Mingyu Xiao

Publication date: 30 June 2017

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmsFPTbalanced separatorslinear kernelsNT-theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing ⋮ Parameterized algorithms for generalizations of directed feedback vertex set ⋮ Political districting to minimize cut edges

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a generalization of Nemhauser and Trotter's local optimization theorem
• On the parameterized complexity of finding separators with non-hereditary properties
• A generalization of Nemhauser and Trotter's local optimization theorem
• Finding odd cycle transversals.
• On the computational complexity of vertex integrity and component order connectivity
• Parameterized graph separation problems
• Simple and improved parameterized algorithms for multiterminal cuts
• Almost 2-SAT is fixed-parameter tractable
• The \(k\)-separator problem: polyhedra, complexity and approximation results
• Crown structures for vertex cover kernelization
• Crown reductions for the minimum weighted vertex cover problem
• Vertex Cover: Further Observations and Further Improvements
• A Polylogarithmic Approximation of the Minimum Bisection
• Finding small balanced separators
• Finding small separators in linear time via treewidth reduction
• An Extension of the Nemhauser–Trotter Theorem to Generalized Vertex Cover with Applications
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Vertex packings: Structural properties and algorithms
• Minimum bisection is fixed parameter tractable
• Multicut is FPT
• Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
• The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Linear kernels for separating a graph into components of bounded size