An Improved Approximation Bound for Spanning Star Forest and Color Saving

DOI10.1007/978-3-642-03816-7_9zbMath1250.68285OpenAlexW1830560292MaRDI QIDQ3182915

Stavros Athanassopoulos, Maria Kyropoulou, Ioannis Caragiannis, Christos Kaklamanis

Publication date: 16 October 2009

Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03816-7_9

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (16)

Tight approximation bounds for combinatorial frugal coverage algorithms ⋮ Improved approximation algorithms for the spanning star forest problem ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ Near-Optimal Asymmetric Binary Matrix Partitions ⋮ Data reductions and combinatorial bounds for improved approximation algorithms ⋮ Improved approximation for spanning star forest in dense graphs ⋮ Near-optimal asymmetric binary matrix partitions ⋮ 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 ⋮ Tight Approximation Bounds for Greedy Frugal Coverage Algorithms ⋮ APPROXIMATING THE SPANNING k-TREE FOREST PROBLEM ⋮ Unnamed Item ⋮ On the star forest polytope for trees and cycles ⋮ Weighted Upper Edge Cover: Complexity and Approximability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Structure preserving reductions among convex optimization problems
• Toward a unified approach for the classification of NP-complete optimization problems
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Differential approximation algorithms for some combinatorial optimization problems
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• z-Approximations
• On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
• A threshold of ln n for approximating set cover
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• Improved Approximation Algorithms for the Spanning Star Forest Problem
• Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment
• Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
• Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs
• Computing and Combinatorics
• Wavelength Management in WDM Rings to Maximize the Number of Connections

This page was built for publication: An Improved Approximation Bound for Spanning Star Forest and Color Saving