Spider covers and their applications (Q1935978): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q202633 |
Changed an Item |
||
Property / author | |||
Property / author: Mikael Hammar / rank | |||
Normal rank |
Revision as of 22:14, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Spider covers and their applications |
scientific article |
Statements
Spider covers and their applications (English)
0 references
21 February 2013
0 references
Summary: We introduce two new combinatorial optimization problems: the \textsc{Maximum Spider} problem and the \textsc{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 \textit{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 \textsc{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 \textit{Maximum Spider} and \textsc{Spider Cover} problems by pointing out a variety of applications. We show that a natural greedy algorithm gives a 2-approximation algorithm for the \textit{Maximum Spider} problem and a \((\log|\mathcal D| + 1)\)-approximation algorithm for the \textsc{Spider Cover} problem.
0 references