Please use this identifier to cite or link to this item:
Fulltext available Open Access
Publisher URL:
arXiv ID: 2207.12278
Title: A survey on graph problems parameterized above and below guaranteed values
Language: English
Authors: Gutin, Gregory Z. 
Mnich, Matthias  
Issue Date: 2022
Source: arXiv: 2207.12278 (2022)
Abstract (english): 
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.
DOI: 10.15480/882.4527
Institute: Algorithmen und Komplexität E-11 
Document Type: Preprint
License: In Copyright In Copyright
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
2207.12278.pdf237,27 kBAdobe PDFView/Open
Show full item record

Page view(s)

checked on Aug 11, 2022


checked on Aug 11, 2022

Google ScholarTM


Note about this record

Cite this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.