More results on the complexity of domination problems in graphs (Q1664084): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q1199621 |
Set OpenAlex properties. |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Property / author | |||
| Property / author: Antoine C. Lobstein / rank | |||
Normal rank | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1504/ijicot.2017.10004701 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2607172406 / rank | |||
Normal rank | |||
Latest revision as of 08:41, 30 July 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | More results on the complexity of domination problems in graphs |
scientific article |
Statements
More results on the complexity of domination problems in graphs (English)
0 references
24 August 2018
0 references
Summary: Given a graph \(G=(V,E)\) and an integer \(r\geq 1\), we call `\(r\)-dominating code' any subset \(C\) of \(V\) such that every vertex in \(V\) is at distance at most \(r\) from at least one vertex in \(C\). We investigate and locate in the complexity classes of the polynomial hierarchy, several problems linked with domination in graphs, such as, given \(r\) and \(G\), the existence of, or search for, optimal \(r\)-dominating codes in \(G\), or optimal \(r\)-dominating codes in \(G\) containing a subset of vertices \(X\subset V\).
0 references
complexity
0 references
complexity classes
0 references
covering radius
0 references
dominating codes
0 references
graph theory
0 references
hardness
0 references
NP-completeness
0 references
polynomial hierarchy
0 references
