# Mixed covering of trees and the augmentation problem with odd diameter constraints

- Authors
- Journal
- Electronic Notes in Discrete Mathematics 1571-0653
- Publisher
- Elsevier
- Publication Date
- Volume
- 22
- Identifiers
- DOI: 10.1016/j.endm.2005.06.068
- Keywords
- Disciplines

## Abstract

Abstract In this talk, we will outline a polynomial time algorithm for solving the problem of partial covering of trees with n 1 balls of radius R 1 and n 2 balls of radius R 2 ( R 1 < R 2 ) so as to maximize the total number of covered vertices. We will then show that the solutions provided by this algorithm in the particular case R 1 = R − 1 , R 2 = R can be used to obtain for any integer δ > 0 a factor ( 2 + 1 δ ) approximation algorithm for solving the following augmentation problem with odd diameter constraints D = 2 R + 1 : given a tree T, add a minimum number of new edges such that the augmented graph has diameter ≤ D. The previous approximation algorithm of Ishii, Yamamoto, and Nagamochi (2003) has factor 8.

## There are no comments yet on this publication. Be the first to share your thoughts.