Improved approximation for spanning star forest in dense graphs
type: Item
instance of: scholarly article
title: Improved approximation for spanning star forest in dense graphs
zbMATH Open document ID: 1268.90114
author: Hongyu Liang
author: Jing (Selena) He
published in: Journal of Combinatorial Optimization
publication date: 2013-03-25T00:00:00Z
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 6148668
zbMATH Keywords: spanning star forest
zbMATH Keywords: dense graph
zbMATH Keywords: approximation algorithm
zbMATH Keywords: hardness of approximation
MaRDI profile type: Publication
full work available at URL: s10878-012-9499-2
OpenAlex ID: W2033780447
cites work: Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
cites work: An Improved Approximation Bound for Spanning Star Forest and Color Saving
cites work: Computing and Combinatorics
cites work: Improved approximation bounds for edge dominating set in dense graphs
cites work: Approximating subdense instances of covering problems
cites work: On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
cites work: Improved Approximation Algorithms for the Spanning Star Forest Problem
cites work: A threshold of ln n for approximating set cover
cites work: Exponential time algorithms for the minimum dominating set problem on some graph classes
cites work: Approximating vertex cover on dense graphs
cites work: Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
cites work: Q4527015
cites work: Problems remaining NP-complette for sparse or dense graphs
cites work: Chebyshev's approximation algorithms and applications
DOI: 10.1007/S10878-012-9499-2
description: scientific article; zbMATH DE number 6148668