A Boundary Property for Upper Domination

DOI10.1007/978-3-319-44543-4_18zbMath1392.68195OpenAlexW2549002970MaRDI QIDQ2819507

Victor Zamaraev, Bernard Ries, Jérôme Monnot, Shahid Hussain, Hassan AbouEisha, Vadim V. Lozin

Publication date: 29 September 2016

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

Full work available at URL: http://doc.rero.ch/record/324600/files/ud-boundary_rero.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (5)

Weighted upper domination number ⋮ The many facets of upper domination ⋮ Upper domination: towards a dichotomy through boundary properties ⋮ Algorithmic aspects of upper edge domination ⋮ Weighted Upper Edge Cover: Complexity and Approximability

Cites Work

• Unnamed Item
• Unnamed Item
• Boundary properties of well-quasi-ordered sets of graphs
• Boundary properties of graphs for algorithmic graph problems
• On the computational complexity of upper fractional domination
• Recent developments on graphs of bounded clique-width
• Contributions to the theory of domination, independence and irredundance in graphs
• Chordal graphs and upper irredundance, upper domination and independence
• Computing independent sets in graphs with large girth
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Boundary classes of graphs for the dominating set problem
• Critical properties of graphs of bounded clique-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Boundary properties of the satisfiability problems
• NP-hard graph problems and boundary classes of graphs
• A Dichotomy for Upper Domination in Monogenic Classes
• Boundary Classes of Planar Graphs
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• Boundary Properties of Factorial Classes of Graphs

This page was built for publication: A Boundary Property for Upper Domination