Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation

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

zbMATH Keywords

upper dominationFPT algorithmssub-exponential approximation

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

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