In)approximability of Maximum Minimal FVS
type: Item
instance of: scholarly article
author: Louis Dublois
author: Tesshu Hanaka
author: Q6065390
author: Michael Lampis
author: Nikolaos Melissinos
publication date: 2023-11-14T00:00:00Z
Mathematics Subject Classification ID: 68Wxx
zbMATH DE Number: 7765361
zbMATH Keywords: approximation algorithms
zbMATH Keywords: ETH
zbMATH Keywords: inapproximability
MaRDI profile type: Publication
full work available at URL: LIPIcs-ISAAC-2020-3.pdf
OpenAlex ID: W3113992694
title: In)approximability of Maximum Minimal FVS
cites work: Upper domination: towards a dichotomy through boundary properties
cites work: Q5874335
cites work: The lazy bureaucrat scheduling problem
cites work: New tools and connections for exponential-time approximation
cites work: The many facets of upper domination
cites work: Q5874480
cites work: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
cites work: Time-approximation trade-offs for inapproximable problems
cites work: On the max min vertex cover problem
cites work: Approximation of min coloring by moderately exponential algorithms
cites work: Weighted upper domination number
cites work: Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
cites work: On the computational complexity of upper fractional domination
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Parameterized Algorithms
cites work: Exponential-time approximation of weighted set cover
cites work: Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
cites work: Exact and approximate bandwidth
cites work: Approximating MAX SAT by moderately exponential and parameterized algorithms
cites work: Q5875545
cites work: Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse
cites work: An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem
cites work: The Lazy Bureaucrat Problem with Common Arrivals and Deadlines: Approximation and Mechanism Design
cites work: On the maximum weight minimal separator
cites work: On the complexity of the upper \(r\)-tolerant edge cover problem
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Algorithmic aspects of upper paired-domination in graphs
cites work: An improved algorithm for parameterized edge dominating set problem
cites work: Chordal graphs and upper irredundance, upper domination and independence
cites work: Improved (In-)approximability bounds for \(d\)-scattered set
cites work: Weighted Upper Edge Cover: Complexity and Approximability
cites work: On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem
cites work: Maximum Minimal Vertex Cover Parameterized by Vertex Cover
cites work: Q3002782
cites work: An induced subgraph characterization of domination perfect graphs
DOI: 10.4230/LIPICS.ISAAC.2020.3
description: scientific article; zbMATH DE number 7765361