Back to Search
Start Over
On the solution bound of two-sided scaffold filling.
- Source :
-
Theoretical Computer Science . Jun2021, Vol. 873, p47-63. 17p. - Publication Year :
- 2021
-
Abstract
- In this paper, we propose an algorithm which approximates the Two-Sided Scaffold Filling problem to a performance ratio 1.4 + ε. This is achieved through a deep investigation of the optimal solution structure of Two-Sided Scaffold Filling. We make use of a relevant graph aiming at a solution of a Two-Sided Scaffold Filling instance, and evaluate the optimal solution value by the number of connected components in this graph. We show that an arbitrary optimal solution can be transformed into one whose relevant graph admits connected components that are available to compare with the solution of our algorithm in terms of their values. The performance ratio 1.4 + ε is obtained by comparing the bound of such an optimal solution with the solution of our algorithm. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH connectivity
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 873
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 150411617
- Full Text :
- https://doi.org/10.1016/j.tcs.2021.04.024