The many facets of upper domination
From MaRDI portal
Publication:1704853
DOI10.1016/J.TCS.2017.05.042zbMATH Open1388.68099OpenAlexW2625060274MaRDI QIDQ1704853FDOQ1704853
Authors: Cristina Bazgan, Ljiljana Brankovic, Katrin Casel, Henning Fernau, Klaus Jansen, Kim-Manuel Klein, Michael Lampis, Mathieu Liedloff, Jérôme Monnot, Vangelis Th. Paschos 
Publication date: 13 March 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2017.05.042
Recommendations
dominating setextension problemsbounded-degree graphs(in)approximabilityfixed parameter (in)tractability
Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Fundamentals of parameterized complexity
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- A partial k-arboretum of graphs with bounded treewidth
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Linear time solvable optimization problems on graphs of bounded clique-width
- Title not available (Why is that?)
- Approximation algorithms for NP-complete problems on planar graphs
- Approximating the minimum maximal independence number
- Improved upper bounds for vertex cover
- Three short proofs in graph theory
- Combinatorial bounds via measure and conquer
- On the enumeration of minimal dominating sets and related notions
- A special planar satisfiability problem and a consequence of its NP- completeness
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- On the parameterized complexity of multiple-interval graph problems
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- The Turing way to parameterized complexity
- Fast algorithms for min independent dominating set
- A dichotomy for upper domination in monogenic classes
- Pathwidth of cubic graphs and exact algorithms
- Inequalities relating domination parameters in cubic graphs
- A faster algorithm for dominating set analyzed by the potential method
- A fine-grained analysis of a simple independent set algorithm
- A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
- Exact algorithms for dominating set
- Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
- Approximating minimum independent dominating sets in wireless networks
- Dual subimplicants of positive Boolean functions
- Contributions to the theory of domination, independence and irredundance in graphs
- The complexity of irredundant sets parameterized by size
- Chordal graphs and upper irredundance, upper domination and independence
- A boundary property for upper domination
- Upper domination: complexity and approximation
- Algorithmic aspects of \textsc{Upper Domination}: a parameterised perspective
- Title not available (Why is that?)
- On the computational complexity of upper fractional domination
- The lazy bureaucrat scheduling problem
- Scheduling algorithms for procrastinators
- Data reductions and combinatorial bounds for improved approximation algorithms
- On the computational complexity of upper total domination
- Maximum minimal vertex cover parameterized by vertex cover
- On the max min vertex cover problem
- Fast algorithms for \textsc{min independent dominating set}
Cited In (36)
- On the complexity of solution extension of optimization problems
- Computing the largest bond and the maximum connected cut of a graph
- Extension and its price for the connected vertex cover problem
- The diversity of domination
- Minimal Roman dominating functions: extensions and enumeration
- Algorithmic aspects of upper paired-domination in graphs
- Upper domination: towards a dichotomy through boundary properties
- Topics on domination
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
- In)approximability of Maximum Minimal FVS
- On the complexity landscape of the domination chain
- On the complexity of minimum maximal acyclic matchings
- Algorithmic aspects of upper edge domination
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- Recognizing well-dominated graphs is coNP-complete
- Weighted upper edge cover: complexity and approximability
- A boundary property for upper domination
- Upper domination: complexity and approximation
- Algorithmic aspects of \textsc{Upper Domination}: a parameterised perspective
- Binary programming formulations for the upper domination problem
- Minimum maximal acyclic matching in proper interval graphs
- (In)approximability of maximum minimal FVS
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- Formalization of the Domination Chain with Weighted Parameters (Short Paper)
- Minimal zero forcing sets
- Weighted upper domination number
- Upper Clique Transversals in Graphs
- Parameterized complexity of computing maximum minimal blocking and hitting sets
- A dichotomy for upper domination in monogenic classes
- Invited talks
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
- Extension of some edge graph problems: standard, parameterized and approximation complexity
- Minimal Roman dominating functions: extensions and enumeration
- On the complexity of minimum maximal acyclic matchings
- Minimum maximal acyclic matching in proper interval graphs
This page was built for publication: The many facets of upper domination
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1704853)
