A primal-dual method for approximating tree cover with two weights

DOI10.1016/J.DISOPT.2006.05.005MaRDI QIDQ2465937zbMATH OpenOpenAlexFDO

Authors Takashi Doi, Toshihiro Fujito

Publication date 11 January 2008

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2006.05.005

zbMATH Keywords

approximation algorithmsprimal-dual methodtree cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover
• Approximating the tree and tour covers of a graph
• How to trim a MST, a 2-approximation algorithm for minimum cost-tree cover

Cites work

• A 2-approximation algorithm for the minimum weight edge dominating set problem
• A new approach to the maximum-flow problem
• Approximating the tree and tour covers of a graph
• Depth-first search and the vertex cover problem
• Geometric algorithms and combinatorial optimization
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• Improved approximations for tour and tree covers
• On approximability of the independent/connected edge dominating set problems
• The Rectilinear Steiner Tree Problem is $NP$-Complete

Cited in

(2)

• How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover
• How to trim a MST, a 2-approximation algorithm for minimum cost-tree cover

This page was built for publication: A primal-dual method for approximating tree cover with two weights

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2465937)