E-viri
Recenzirano
-
Chaudhary, Juhi; Pradhan, Dinabandhu
Discrete Applied Mathematics, 09/2024, Letnik: 354Journal Article
A Roman{3}-dominating function on a graph G is a function f:V(G)→{0,1,2,3} having the property that for any vertex u∈V(G), if f(u)=0, then ∑v∈NG(u)f(v)≥3, and if f(u)=1, then ∑v∈NG(u)f(v)≥2. The weight of a Roman {3}-dominating function f is the sum f(V(G))=∑v∈V(G)f(v) and the minimum weight of a Roman {3}-dominating function on G is called the Roman{3}-domination number of G and is denoted by γ{R3}(G). Given a graph G, Roman{3}-domination asks to find the minimum weight of a Roman {3}-dominating function on G. In this paper, we study the algorithmic aspects of Roman{3}-domination on various graph classes. We show that the decision version of Roman{3}-domination remains NP-complete for chordal bipartite graphs, planar graphs, star-convex bipartite graphs, and chordal graphs. We show that Roman{3}-domination cannot be approximated within a ratio of (13−ɛ)ln|V(G)| for any ɛ>0 unless P=NP for bipartite graphs as well as chordal graphs, whereas Roman{3}-domination can be approximated within a factor of O(lnΔ) for graphs having maximum degree Δ. We also show that Roman{3}-domination is APX-complete for graphs with maximum degree 4. On the positive side, we show that Roman{3}-domination can be solved in linear time for chain graphs and cographs.
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|
Vir: Osebne bibliografije
in: SICRIS
To gradivo vam je dostopno v celotnem besedilu. Če kljub temu želite naročiti gradivo, kliknite gumb Nadaljuj.