In)approximability of Maximum Minimal FVS
From MaRDI portal
Publication:6065391
DOI10.4230/lipics.isaac.2020.3OpenAlexW3113992694MaRDI QIDQ6065391
Louis Dublois, Unnamed Author, Nikolaos Melissinos, Tesshu Hanaka, Michael Lampis
Publication date: 14 November 2023
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/13347/pdf/LIPIcs-ISAAC-2020-3.pdf/
Related Items (2)
Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- On the max min vertex cover problem
- Exact and approximate bandwidth
- Upper domination: towards a dichotomy through boundary properties
- On the computational complexity of upper fractional domination
- Approximation of min coloring by moderately exponential algorithms
- Exponential-time approximation of weighted set cover
- Chordal graphs and upper irredundance, upper domination and independence
- The lazy bureaucrat scheduling problem
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Time-approximation trade-offs for inapproximable problems
- An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem
- The many facets of upper domination
- Linear time solvable optimization problems on graphs of bounded clique-width
- On the complexity of the upper \(r\)-tolerant edge cover problem
- Improved (In-)approximability bounds for \(d\)-scattered set
- New tools and connections for exponential-time approximation
- Algorithmic aspects of upper paired-domination in graphs
- On the maximum weight minimal separator
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Weighted upper domination number
- On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem
- An Improved Algorithm for Parameterized Edge Dominating Set Problem
- The Lazy Bureaucrat Problem with Common Arrivals and Deadlines: Approximation and Mechanism Design
- Maximum Minimal Vertex Cover Parameterized by Vertex Cover
- Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse
- An induced subgraph characterization of domination perfect graphs
- Weighted Upper Edge Cover: Complexity and Approximability
- Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
This page was built for publication: In)approximability of Maximum Minimal FVS
