Options
A survey on graph problems parameterized above and below guaranteed values
Citation Link: https://doi.org/10.15480/882.4527
Publikationstyp
Preprint
Date Issued
2022
Sprache
English
Author(s)
Institut
TORE-DOI
We survey the field of algorithms and complexity for graph problems parameterized above or below guaranteed values, a research area which was pioneered by Venkatesh Raman. Those problems seek, for a given graph G, a solution whose value is at least g(G)+k or at most g(G)−k, where g(G) is a guarantee on the value that any solution on G takes. The goal is to design algorithms which find such solution in time whose complexity in k is decoupled from that in the guarantee, or to rule out the existence of such algorithms by means of intractability results.
We discuss a large number of algorithms and intractability results, and complement them by several open problems.
We discuss a large number of algorithms and intractability results, and complement them by several open problems.
DDC Class
510: Mathematik
Loading...
Name
2207.12278.pdf
Size
237.27 KB
Format
Adobe PDF