Upper domination: towards a dichotomy through boundary properties
type: Item
instance of: scholarly article
title: Upper domination: towards a dichotomy through boundary properties
zbMATH Open document ID: 1391.05241
author: Hassan AbouEisha
author: Shahid Hussain
author: Vadim Lozin
author: Jérôme Monnot
author: Bernard Ries
author: Victor Zamaraev
published in: Algorithmica
publication date: 2018-07-26T00:00:00Z
full work available at URL: https://arxiv.org/abs/1609.01510
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6911188
zbMATH Keywords: upper dominating set
zbMATH Keywords: boundary class
zbMATH Keywords: complexity dichotomy
zbMATH Keywords: NP-hardness
MaRDI profile type: Publication
OpenAlex ID: W2964110022
arXiv ID: 1609.01510
cites work: A Dichotomy for Upper Domination in Monogenic Classes
cites work: A Boundary Property for Upper Domination
cites work: On easy and hard hereditary classes of graphs with respect to the independent set problem
cites work: Boundary classes of graphs for the dominating set problem
cites work: NP-hard graph problems and boundary classes of graphs
cites work: Algorithmic Aspects of Upper Domination: A Parameterised Perspective
cites work: Upper Domination: Complexity and Approximation
cites work: Clique-width for 4-vertex forbidden subgraphs
cites work: On the computational complexity of upper fractional domination
cites work: Contributions to the theory of domination, independence and irredundance in graphs
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Upper bounds to the clique width of graphs
cites work: Some simplified NP-complete graph problems
cites work: Q3785978
cites work: Chordal graphs and upper irredundance, upper domination and independence
cites work: Recent developments on graphs of bounded clique-width
cites work: Q3353058
cites work: Boundary properties of graphs for algorithmic graph problems
cites work: Boundary properties of well-quasi-ordered sets of graphs
cites work: Boundary Classes of Planar Graphs
cites work: Critical properties of graphs of bounded clique-width
cites work: Boundary properties of the satisfiability problems
cites work: On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
cites work: Boundary Properties of Factorial Classes of Graphs
cites work: Independent sets in extensions of 2\(K_{2}\)-free graphs
cites work: Computing independent sets in graphs with large girth
cites work: Graph minors. V. Excluding a planar graph
DOI: 10.1007/S00453-017-0346-9
description: scientific article