Content deleted Content added
Added illustration of the disk covering problem and a description. |
m Open access bot: url-access=subscription updated in citation with #oabot. |
||
Line 70:
* A rainbow set is a conflict-free set in the special case in which ''G<sub>O</sub>'' is made of disjoint cliques, where each clique represents a color.
''Conflict-free set cover'' is the problem of finding a conflict-free subset of ''O'' that is a covering of ''P''. Banik, Panolan, Raman, Sahlot and Saurabh<ref>{{Cite journal|last1=Banik|first1=Aritra|last2=Panolan|first2=Fahad|last3=Raman|first3=Venkatesh|last4=Sahlot|first4=Vibha|last5=Saurabh|first5=Saket|date=2020-01-01|title=Parameterized Complexity of Geometric Covering Problems Having Conflicts|url=https://doi.org/10.1007/s00453-019-00600-w|journal=Algorithmica|language=en|volume=82|issue=1|pages=1–19|doi=10.1007/s00453-019-00600-w|s2cid=254027914 |issn=1432-0541|url-access=subscription}}</ref> [[mathematical proof|prove]] the following for the special case in which the conflict-graph has bounded [[arboricity]]:
* If the geometric cover problem is [[Fixed-parameter algorithm|fixed-parameter]] tractable (FPT), then the conflict-free geometric cover problem is FPT.
| |||