Upper domination: towards a dichotomy through boundary properties
From MaRDI portal
Publication:722525
DOI10.1007/s00453-017-0346-9zbMath1391.05241arXiv1609.01510OpenAlexW2964110022MaRDI QIDQ722525
Jérôme Monnot, Vadim V. Lozin, Shahid Hussain, Hassan AbouEisha, Bernard Ries, Victor Zamaraev
Publication date: 26 July 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1609.01510
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (5)
Between clique-width and linear clique-width of bipartite graphs ⋮ In)approximability of Maximum Minimal FVS ⋮ Algorithmic aspects of upper edge domination ⋮ (In)approximability of maximum minimal FVS ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
Cites Work
- 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
- Graph minors. V. Excluding a planar graph
- 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
- Some simplified NP-complete graph problems
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- 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
- Clique-width for 4-vertex forbidden subgraphs
- Boundary properties of the satisfiability problems
- NP-hard graph problems and boundary classes of graphs
- A Boundary Property for Upper Domination
- Upper Domination: Complexity and Approximation
- Algorithmic Aspects of Upper Domination: A Parameterised Perspective
- 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
- Unnamed Item
- Unnamed Item
This page was built for publication: Upper domination: towards a dichotomy through boundary properties
