Please use this identifier to cite or link to this item: https://doi.org/10.15480/882.4527
Fulltext available Open Access
Publisher URL: https://arxiv.org/abs/2207.12278
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.
URI: http://hdl.handle.net/11420/13299
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
Thumbnail
Show full item record

Page view(s)

33
checked on Aug 11, 2022

Download(s)

2
checked on Aug 11, 2022

Google ScholarTM

Check

Note about this record

Cite this record

Export

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