Affordable Access

Publisher Website

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
  • Partial Covering
  • Diameter
  • Augmentation Problem
  • Dynamical Programming
  • Approximation Algorithms
Disciplines
  • Computer Science

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.