E-viri
Recenzirano
-
Brandstädt, Andreas; Mosca, Raffaele
Theoretical computer science, 07/2021, Letnik: 878-879Journal Article
The Maximum Weight Independent Set (MWIS) problem on finite undirected graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum weight sum. MWIS is one of the most investigated and most important algorithmic graph problems; it is well known to be NP-complete, and it remains NP-complete even under various strong restrictions such as for triangle-free graphs. Its complexity for Pk-free graphs, k≥7, is an open problem. In 7, it is shown that MWIS can be solved in polynomial time for (P7,triangle)-free graphs. This result is extended by Maffray and Pastor 22 showing that MWIS can be solved in polynomial time for (P7,bull)-free graphs. In the same paper, they also showed that MWIS can be solved in polynomial time for (S1,2,3,bull)-free graphs. In this paper, using a similar approach as in 7, we show that MWIS can be solved in polynomial time for (S1,2,4,triangle)-free graphs which generalizes the result for (P7,triangle)-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.