Boundary classes of graphs for the dominating set problem

DOI10.1016/J.DISC.2004.04.010MaRDI QIDQ1877644zbMATH OpenOpenAlexFDO

Authors Dmitry V. Korobitsyn, Vadim Lozin, V. E. Alekseev

Publication date 19 August 2004

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2004.04.010

zbMATH Keywords

Computational complexityDominating setHereditary class

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• scientific article; zbMATH DE number 7742925
• A complexity dichotomy and a new boundary class for the dominating set problem
• Boundary Classes of Planar Graphs
• Upper domination: towards a dichotomy through boundary properties
• NP-hard graph problems and boundary classes of graphs

Cites work

• scientific article; zbMATH DE number 4204394 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 468640 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• A New Algorithm for Generating All the Maximal Independent Sets
• An upper bound on the number of cliques in a graph
• Computing independent sets in graphs with large girth
• On easy and hard hereditary classes of graphs with respect to the independent set problem

Cited in

(33)

• A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
• Vertex coloring of graphs with few obstructions
• scientific article; zbMATH DE number 7742925 (Why is no real title available?)
• The coloring problem for classes with two small obstructions
• Boundary properties of graphs for algorithmic graph problems
• Complete complexity dichotomies for the dominating set problem
• Critical properties of bipartite permutation graphs
• Critical elements in combinatorially closed families of graph classes
• Boundary Classes of Planar Graphs
• Upper domination: towards a dichotomy through boundary properties
• Exploiting c-Closure in Kernelization Algorithms for Graph Problems
• \textsc{max-cut} and containment relations in graphs
• Max-Cut and containment relations in graphs
• On the number of boundary classes in the 3-colouring problem
• The width and integer optimization on simplices with bounded minors of the constraint matrices
• Boundary classes for graph problems involving non-local properties
• A study of the boundary graph classes for colorability problems
• Critical hereditary graph classes: a survey
• A complexity dichotomy and a new boundary class for the dominating set problem
• On the complexity of the dominating induced matching problem in hereditary classes of graphs
• The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
• A boundary property for upper domination
• Boundary graph classes for some maximum induced subgraph problems
• NP-hard graph problems and boundary classes of graphs
• Exploiting c-closure in kernelization algorithms for graph problems
• scientific article; zbMATH DE number 6004968 (Why is no real title available?)
• Boundary classes of graphs for some recognition problems
• A decidability result for the dominating set problem
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• scientific article; zbMATH DE number 992954 (Why is no real title available?)
• Boundary properties of factorial classes of graphs
• Boundary properties of well-quasi-ordered sets of graphs
• Solving problems on graphs of high rank-width

This page was built for publication: Boundary classes of graphs for the dominating set problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1877644)