A complexity dichotomy and a new boundary class for the dominating set problem
From MaRDI portal
Publication:328713
DOI10.1007/s10878-015-9872-zzbMath1354.90111MaRDI QIDQ328713
Publication date: 20 October 2016
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-015-9872-z
Related Items
Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Unnamed Item, Critical properties of bipartite permutation graphs, On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems, On lattice point counting in \(\varDelta\)-modular polyhedra, FPT-algorithm for computing the width of a simplex given by a convex hull, Boundary classes for graph problems involving non-local properties, Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Vertex coloring of graphs with few obstructions
- Coloring graphs characterized by a forbidden subgraph
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Dominating sets for split and bipartite graphs
- New graph classes of bounded clique-width
- The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
- Unit disk graphs
- Dominating cliques in \(P_ 5\)-free graphs
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- 4-coloring \(H\)-free graphs when \(H\) is small
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- Boundary classes of graphs for the dominating set problem
- Domination and total domination on asteroidal triple-free graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
- NP-hard graph problems and boundary classes of graphs
- List coloring in the absence of two subgraphs
- A Dichotomy for Upper Domination in Monogenic Classes
- Boundary Classes of Planar Graphs
- Edge Dominating Sets in Graphs
- On the complexity of domination number determination in monogenic classes of graphs
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs
- Classes of graphs critical for the edge list-ranking problem
- Independent Set in P5-Free Graphs in Polynomial Time
