A complexity dichotomy and a new boundary class for the dominating set problem
type: Item
instance of: scholarly article
title: A complexity dichotomy and a new boundary class for the dominating set problem
zbMATH Open document ID: 1354.90111
published in: Journal of Combinatorial Optimization
publication date: 2016-10-20T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 6641536
zbMATH Keywords: dominating set
zbMATH Keywords: computational complexity
zbMATH Keywords: polynomial-time algorithm
zbMATH Keywords: boundary class
author: D. S. Malyshev
MaRDI profile type: Publication
full work available at URL: s10878-015-9872-z
OpenAlex ID: W2047820500
cites work: A Dichotomy for Upper Domination in Monogenic Classes
cites work: The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
cites work: Polynomial algorithm for finding the largest independent sets in graphs without forks
cites work: On easy and hard hereditary classes of graphs with respect to the independent set problem
cites work: NP-hard graph problems and boundary classes of graphs
cites work: Boundary classes of graphs for the dominating set problem
cites work: Dominating cliques in \(P_ 5\)-free graphs
cites work: Dominating sets for split and bipartite graphs
cites work: New graph classes of bounded clique-width
cites work: Updating the complexity status of coloring graphs without a fixed induced linear forest
cites work: Unit disk graphs
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Q4198056
cites work: List coloring in the absence of two subgraphs
cites work: Coloring graphs characterized by a forbidden subgraph
cites work: 4-coloring \(H\)-free graphs when \(H\) is small
cites work: Boundary Classes of Planar Graphs
cites work: On the complexity of domination number determination in monogenic classes of graphs
cites work: Q4448764
cites work: Domination and total domination on asteroidal triple-free graphs
cites work: Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs
cites work: Independent Set in P5-Free Graphs in Polynomial Time
cites work: Vertex coloring of graphs with few obstructions
cites work: Independent sets in extensions of 2\(K_{2}\)-free graphs
cites work: The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
cites work: Classes of graphs critical for the edge list-ranking problem
cites work: Edge Dominating Sets in Graphs
cites work: Q4405639
DOI: 10.1007/S10878-015-9872-Z
description: scientific article; zbMATH DE number 6641536