A Further Improved Approximation Algorithm for Breakpoint Graph Decomposition期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

A Further Improved Approximation Algorithm for Breakpoint Graph Decomposition

Authors:	Guohui Lin Tao Jiang

Institution:	(1) Deparment of Computing Science, University of Alberta, Edmonton, Alberta, T6G 2E8, Canada;(2) Deparment of Computing Science, University of California, Riverside, CA, 92521, Canada

Abstract:	Breakpoint graph decomposition is a crucial step in all recent approximation algorithms for SORTING BY REVERSALS, which is one of the best-known algorithmic problems in computational molecular biology. Caprara and Rizzi recently improved the approximation ratio for breakpoint graph decomposition from $\frac{3}{2}$ to $\frac{{33}}{{23}}$ + 1.4348 + , for any positive . In this paper, we extend the techniques of Caprara and Rizzi and incorporate a balancing argument to further improve the approximation ratio to $\frac{{5073 - \sqrt {1201} }}{{3208}}$ + 1.4193 + , for any positive . These improvements imply improved approximation results for SORTING BY REVERSALS for almost all random permutations.

Keywords:	genome rearrangement sorting by reversals breakpoint graph alternating cycle decomposition maximum independent set k-set packing approximation algorithm
本文献已被 SpringerLink 等数据库收录！