Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
From MaRDI portal
Publication:5925558
DOI10.1016/j.tcs.2022.05.013OpenAlexW3121994163WikidataQ114129104 ScholiaQ114129104MaRDI QIDQ5925558
Louis Dublois, Michael Lampis, Vangelis Th. Paschos
Publication date: 13 June 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2101.07550
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating the minimum maximal independence number
- On the computational complexity of upper fractional domination
- Strong computational lower bounds via parameterized complexity
- Approximating minimum independent dominating sets in wireless networks
- The lazy bureaucrat scheduling problem
- Structurally parameterized \(d\)-Scattered Set
- An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem
- The many facets of upper domination
- Fast algorithms for min independent dominating set
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- On the maximum weight minimal separator
- On subexponential and FPT-time inapproximability
- The Lazy Bureaucrat Problem with Common Arrivals and Deadlines: Approximation and Mechanism Design
- Maximum Minimal Vertex Cover Parameterized by Vertex Cover
- On the max min vertex cover Problem
- Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
- Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
- Parameterized Algorithms
- On cliques in graphs
- In)approximability of Maximum Minimal FVS
This page was built for publication: Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
