Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
From MaRDI portal
Publication:3631898
DOI10.1137/070682150zbMath1187.68251OpenAlexW1983741169MaRDI QIDQ3631898
C. Thach Nguyen, Louxin Zhang, Minmei Hou, Webb Miller, Jian Shen, Li Sheng
Publication date: 22 June 2009
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/070682150
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (18)
An Improved Approximation Bound for Spanning Star Forest and Color Saving ⋮ Improved approximation algorithms for the spanning star forest problem ⋮ Approximation algorithms for the maximum carpool matching problem ⋮ Approximating the Spanning k-Tree Forest Problem ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ Complexity and approximability of extended spanning star forest problems in general and complete graphs ⋮ Data reductions and combinatorial bounds for improved approximation algorithms ⋮ Improved approximation for spanning star forest in dense graphs ⋮ Local search algorithms for the maximum carpool matching problem ⋮ On the \(k\)-edge-incident subgraph problem and its variants ⋮ Combinatorics for smaller kernels: the differential of a graph ⋮ On Variants of the Spanning Star Forest Problem ⋮ APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM ⋮ On the Complexity Landscape of the Domination Chain ⋮ Unnamed Item ⋮ Weighted Upper Edge Cover: Complexity and Approximability ⋮ The complexity of finding harmless individuals in social networks ⋮ The maximum weight spanning star forest problem on cactus graphs
This page was built for publication: Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
