A complexity dichotomy and a new boundary class for the dominating set problem (Q328713): Difference between revisions

@@ Property / author @@
+Dmitriy S. Malyshev
@@ Property / author: Dmitriy S. Malyshev / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s10878-015-9872-z
+Normal rank
@@ Property / OpenAlex ID @@
+W2047820500
@@ Property / OpenAlex ID: W2047820500 / rank @@
+Normal rank
@@ Property / cites work @@
+A Dichotomy for Upper Domination in Monogenic Classes
+Normal rank
@@ Property / cites work @@
+The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
+Normal rank
@@ Property / cites work @@
+Polynomial algorithm for finding the largest independent sets in graphs without forks
+Normal rank
@@ Property / cites work @@
+On easy and hard hereditary classes of graphs with respect to the independent set problem
+Normal rank
@@ Property / cites work @@
+NP-hard graph problems and boundary classes of graphs
+Normal rank
@@ Property / cites work @@
+Boundary classes of graphs for the dominating set problem
+Normal rank
@@ Property / cites work @@
+Dominating cliques in \(P_ 5\)-free graphs
@@ Property / cites work: Dominating cliques in \(P_ 5\)-free graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Dominating sets for split and bipartite graphs
@@ Property / cites work: Dominating sets for split and bipartite graphs / rank @@
+Normal rank
@@ Property / cites work @@
+New graph classes of bounded clique-width
@@ Property / cites work: New graph classes of bounded clique-width / rank @@
+Normal rank
@@ Property / cites work @@
+Updating the complexity status of coloring graphs without a fixed induced linear forest
+Normal rank
@@ Property / cites work @@
+Unit disk graphs
@@ Property / cites work: Unit disk graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Linear time solvable optimization problems on graphs of bounded clique-width
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+List coloring in the absence of two subgraphs
@@ Property / cites work: List coloring in the absence of two subgraphs / rank @@
+Normal rank
@@ Property / cites work @@
+Coloring graphs characterized by a forbidden subgraph
+Normal rank
@@ Property / cites work @@
+-coloring \(H\)-free graphs when \(H\) is small
@@ Property / cites work: 4-coloring \(H\)-free graphs when \(H\) is small / rank @@
+Normal rank
@@ Property / cites work @@
+Boundary Classes of Planar Graphs
@@ Property / cites work: Boundary Classes of Planar Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of domination number determination in monogenic classes of graphs
+Normal rank
@@ Property / cites work @@
+Q4448764
@@ Property / cites work: Q4448764 / rank @@
+Normal rank
@@ Property / cites work @@
+Domination and total domination on asteroidal triple-free graphs
+Normal rank
@@ Property / cites work @@
+Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs
+Normal rank
@@ Property / cites work @@
+Independent Set in <i>P</i><sub>5</sub>-Free Graphs in Polynomial Time
+Normal rank
@@ Property / cites work @@
+Vertex coloring of graphs with few obstructions
@@ Property / cites work: Vertex coloring of graphs with few obstructions / rank @@
+Normal rank
@@ Property / cites work @@
+Independent sets in extensions of 2\(K_{2}\)-free graphs
+Normal rank
@@ Property / cites work @@
+The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
+Normal rank
@@ Property / cites work @@
+Classes of graphs critical for the edge list-ranking problem
+Normal rank
@@ Property / cites work @@
+Edge Dominating Sets in Graphs
@@ Property / cites work: Edge Dominating Sets in Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q4405639
@@ Property / cites work: Q4405639 / rank @@
+Normal rank