Upper Domination: Complexity and Approximation

DOI10.1007/978-3-319-44543-4_19zbMath1478.68099OpenAlexW2531379207MaRDI QIDQ2819508

Mathieu Liedloff, Henning Fernau, Ljiljana Brankovic, Vangelis Th. Paschos, Katrin Casel, Michael Lampis, Kim-Manuel Klein, Jérôme Monnot, Klaus Jansen, Cristina Bazgan

Publication date: 29 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/15822

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items

Weighted upper domination number, An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem, THE MINIMAL DOMINATING SETS IN A DIRECTED GRAPH AND THE KEY INDICATORS SET OF SOCIO–ECONOMIC SYSTEM, The many facets of upper domination, Upper domination: towards a dichotomy through boundary properties, Algorithmic aspects of upper paired-domination in graphs, Algorithmic aspects of upper edge domination

Cites Work

• Unnamed Item
• Unnamed Item
• Approximating the minimum maximal independence number
• On the computational complexity of upper fractional domination
• Scheduling algorithms for procrastinators
• Approximating minimum independent dominating sets in wireless networks
• Contributions to the theory of domination, independence and irredundance in graphs
• Chordal graphs and upper irredundance, upper domination and independence
• Optimization, approximation, and complexity classes
• Three short proofs in graph theory
• A partial k-arboretum of graphs with bounded treewidth
• A special planar satisfiability problem and a consequence of its NP- completeness
• The lazy bureaucrat scheduling problem
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Inequalities relating domination parameters in cubic graphs
• Fast algorithms for min independent dominating set
• Linear time solvable optimization problems on graphs of bounded clique-width
• A Dichotomy for Upper Domination in Monogenic Classes
• Maximum Minimal Vertex Cover Parameterized by Vertex Cover
• On the max min vertex cover Problem
• Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs
• Fast Algorithms for min independent dominating set
• Approximation algorithms for NP-complete problems on planar graphs
• Dual subimplicants of positive Boolean functions
• On the Enumeration of Minimal Dominating Sets and Related Notions