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

DOI10.1016/j.disopt.2006.05.005zbMath1128.68074OpenAlexW2162786549MaRDI QIDQ2465937

Toshihiro Fujito, Takashi Doi

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

primal-dual methodapproximation algorithmstree cover

Mathematics Subject Classification ID

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

Cites Work

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

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