Spider Covers and Their Applications. (28th November 2012)

• Record Type: Journal Article
• Authors: De Santis, Filomena; Gargano, Luisa; Hammar, Mikael; Negro, Alberto; Vaccaro, Ugo
• Other Names: Hahn G. Academic Editor.; Klostermeyer W. F. Academic Editor.
• Is Part Of: ISRN discrete mathematics. Volume 2012(2012)
• Publication Date: 2012-11-28
• Subjects: Discrete mathematics -- Periodicals; Computer science -- Mathematics; Computer science -- Mathematics; Periodicals; 511.1
• DOI: 10.5402/2012/347430
• Languages: English
• ISSNs: 2090-7788

Abstract

Abstract : We introduce two new combinatorial optimization problems: the Maximum Spider Problem and the Spider Cover Problem; we study their approximability and illustrate their applications. In these problems we are given a directed graph G = ( V, E ), a distinguished vertex s, and a family D of subsets of vertices. A spider centered at vertex s is a collection of arc-disjoint paths all starting at s but ending into pairwise distinct vertices. We say that a spider covers a subset of vertices X if at least one of the endpoints of the paths constituting the spider other than s belongs to X. In the Maximum Spider Problem the goal is to find a spider centered at s that covers the maximum number of elements of the family D. Conversely, the Spider Cover Problem consists of finding the minimum number of spiders centered at s that covers all subsets in D. We motivate the study of the Maximum Spider and Spider Cover Problems by pointing out a variety of applications. We show that a natural greedy algorithm gives a 2-approximation algorithm for the Maximum Spider Problem and a ( log | 𝒟 | + 1 ) -approximation algorithm for the Spider Cover Problem.