E-viri
Recenzirano
Odprti dostop
-
Hanaka, Tesshu; Nishimura, Naomi; Ono, Hirotaka
Discrete Applied Mathematics, 04/2019, Letnik: 259Journal Article
In this paper, we study covering and domination problems on directed graphs. Although undirected Vertex Cover and Edge Dominating Set are well-studied classical graph problems, the directed versions have not been studied much due to the lack of clear definitions. We give natural definitions for Directedr-In (Out) Vertex Cover and Directed(p,q)-Edge Dominating Set as directed generalizations of Vertex Cover and Edge Dominating Set. For these problems, we show that (1) Directedr-In (Out) Vertex Cover and Directed(p,q)-Edge Dominating Set are NP-complete on planar directed acyclic graphs except when r=1 or (p,q)=(0,0), (2) if r≥2, Directedr-In (Out) Vertex Cover is W2-hard and clnk-inapproximable on directed acyclic graphs, (3) if either p or q is greater than 1, Directed(p,q)-Edge Dominating Set is W2-hard and clnk-inapproximable on directed acyclic graphs, (4) all problems can be solved in polynomial time on trees, and (5) Directed(0,1)-Edge ((1,0)-Edge, (1,1)-Edge) Dominating Set is fixed-parameter tractable on general graphs. The first result implies that Directedr-Dominating Set on directed line graphs is NP-complete even if r=1.
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.