Abstract
H. Xu, X.-Z. Wu, C. Cheng, S. Koenig and S. Kumar. The Buss Reduction for the k-Weighted Vertex Cover Problem. In International Symposium on Artificial Intelligence and Mathematics (ISAIM), 2018.Abstract: The k-vertex cover (k-VC) problem is to find a VC of cardinality no more than k on a given undirected graph, and the k-weighted VC (k-WVC) problem is to find a VC of a weight no more than k on a given vertex-weighted undirected graph. In this paper, we generalize the Buss reduction, an important kernelization technique for the k-VC problem, to the k-WVC problem. We study its properties for the k-VC problem and the k-WVC problem on surrogates of large real-world graphs that are generated using the Erdos-Renyi model and the Barabasi-Albert model. We also argue that our study of the Buss reduction bears important implications on the kernelization of combinatorial problems that have been shown to be reducible to WVC problems.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.