Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
From MaRDI portal
Publication:5925677
DOI10.1007/978-3-030-75242-2_14OpenAlexW3165049892MaRDI QIDQ5925677
Vangelis Th. Paschos, Michael Lampis, Louis Dublois
Publication date: 22 March 2023
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-030-75242-2_14
Related Items
(In)approximability of maximum minimal FVS, Efficiently enumerating hitting sets of hypergraphs arising in data profiling
Cites Work
- 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
- 45th International Colloquium on Automata, Languages, and Programming: ICALP 2018, Prague, Czech Republic, July 9-13, 2018
- Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
- Parameterized Algorithms
- In)approximability of Maximum Minimal FVS
