KERNELIZATION ALGORITHMS FOR A GENERALIZATION OF THE COMPONENT ORDER CONNECTIVITY PROBLEM

DOI Web Site Web Site 10 References Open Access

Search this article

Abstract

<p>In the component order connectivity problem, we are given a finite undirected graph G = (V,E) and non-negative integers k, ℓ. The goal of this problem is to determine whether there exists a subset S ⊆ V such that |S| ≤ k and the size of every connected component of the subgraph of G induced by V \ S is at most ℓ. In this paper, we consider the generalization of the component order connectivity problem where the condition on the sizes of connected components is generalized by non-decreasing subadditive functions defined on the subsets of V. We prove that the kernelization techniques for the component order connectivity problem proposed by Xiao can be generalized to our setting.</p>

Journal

References(10)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top