Boundary classes of graphs for the dominating set problem
From MaRDI portal
Publication:1877644
DOI10.1016/j.disc.2004.04.010zbMath1121.05081OpenAlexW1971868915MaRDI QIDQ1877644
Dmitry V. Korobitsyn, Vadim V. Lozin, Vladimir 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
Related Items (27)
Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems ⋮ The width and integer optimization on simplices with bounded minors of the constraint matrices ⋮ A complexity dichotomy and a new boundary class for the dominating set problem ⋮ Vertex coloring of graphs with few obstructions ⋮ Boundary classes for graph problems involving non-local properties ⋮ Boundary properties of well-quasi-ordered sets of graphs ⋮ On the number of boundary classes in the 3-colouring problem ⋮ A decidability result for the dominating set problem ⋮ Critical properties of bipartite permutation graphs ⋮ \textsc{max-cut} and containment relations in graphs ⋮ Solving problems on graphs of high rank-width ⋮ Unnamed Item ⋮ Boundary graph classes for some maximum induced subgraph problems ⋮ The coloring problem for classes with two small obstructions ⋮ Exploiting c-Closure in Kernelization Algorithms for Graph Problems ⋮ NP-hard graph problems and boundary classes of graphs ⋮ Critical hereditary graph classes: a survey ⋮ Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles ⋮ Boundary properties of graphs for algorithmic graph problems ⋮ On the complexity of the dominating induced matching problem in hereditary classes of graphs ⋮ max-cut and Containment Relations in Graphs ⋮ Upper domination: towards a dichotomy through boundary properties ⋮ A Boundary Property for Upper Domination ⋮ Boundary Properties of Factorial Classes of Graphs ⋮ Critical elements in combinatorially closed families of graph classes ⋮ The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs ⋮ A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing independent sets in graphs with large girth
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- A New Algorithm for Generating All the Maximal Independent Sets
- An upper bound on the number of cliques in a graph
This page was built for publication: Boundary classes of graphs for the dominating set problem
