A Study of the Spanning Star Forest Problem on Bipartiteraphs
Date Issued
2008
Date
2008
Author(s)
Lin, Yen-Yi
Abstract
We study the spanning star forest problem (SSF) and its variation on bipartite graphs (BSSF). The relation between SSF and the dominating set problem (DOM), which has fruitful results in the literature, has been observed. The related optimization problems MSSF and MBSSF are of NP-Hard in general, and we hope to contribute to the issues by concentrating on theoretical aspects of approximation algorithms and combinatorial optimization.n this thesis we demonstrate a general framework for approximating MBSSF based on available results of the dominating set problem. We hope to solve this problem by the upper bounds of the domination number. Based on several available domination numbers with constraints, we devise a polynomial time algorithm which obtains a 0.67 approximation ratio for most instances. We also construct some combinatorial witness of such a dominating set efficiently. By extending the dominating set to corresponding spanning star forest, we claim to have efficient algorithms for MBSSF.
Subjects
combinatorial optimization
approximation algorithms
bipartite graph
spanning star forest
dominating set
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R95922101-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):588912e32f521ff1cac09fe0ad70b4b8