E-viri
Recenzirano
Odprti dostop
-
Brandstädt, Andreas; Mosca, Raffaele
Discrete Applied Mathematics, 03/2018, Letnik: 237Journal Article
For a finite, simple, undirected graph G with a vertex weight function, the Maximum Weight Independent Set (MWIS) problem asks for an independent vertex set of G with maximum weight. MWIS is a well-known NP-hard problem of fundamental importance. For claw-free graphs, MWIS can be solved in polynomial time—in 1980, the first two such algorithms were independently found by Minty for MWIS and by Sbihi for the unweighted case. For a constant ℓ≥2, let ℓG denote the disjoint union of ℓ copies of G. In this paper, using a dynamic programming approach (inspired by Farber’s result about MWIS for 2K2-free graphs), we show that for any fixed ℓ, MWIS can be solved in polynomial time for ℓclaw-free graphs. This solves the open cases for MWIS on (P3+claw)-free graphs and on (2K2+claw)-free graphs and extends known results for claw-free graphs, ℓK2-free graphs, (K2+claw)-free graphs, and ℓP3-free graphs.
![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.