Spider covers and their applications (Q1935978): Difference between revisions
From MaRDI portal
Created claim: MaRDI profile type (P1460): MaRDI publication profile (Q5976449), #quickstatements; #temporary_batch_1710401496743 |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.5402/2012/347430 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2152092782 / rank | |||
Normal rank |
Revision as of 21:12, 19 March 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