(UL)
-
Minimum connected transversals in graphs : new hardness results and tractable cases using the price of connectivityChiarelli, Nina ...We perform a systematic study in the computational complexity of the connected variant of three related transversal problems: Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. Just like ... their original counterparts, these variants are NP-complete for general graphs. A graph ▫$G$▫ is ▫$H$▫-free for some graph ▫$H$▫ if ▫$G$▫ contains no induced subgraph isomorphic to ▫$H$▫. It is known that Connected Vertex Cover is NP-complete even for ▫$H$▫-free graphs if ▫$H$▫ contains a claw or a cycle. We show that the two other connected variants also remain NP-complete if ▫$H$▫ contains a cycle or claw. In the remaining case ▫$H$▫ is a linear forest. We show that Connected Vertex Cover, Connected Feedback Vertex Set, and Connected Odd Cycle Transversal are polynomial-time solvable for ▫$sP_2$▫-free graphs for every constant ▫$s \geq 1$▫. For proving these results we use known results on the price of connectivity for vertex cover, feedback vertex set, and odd cycle transversal. This is the first application of the price of connectivity that results in polynomial-time algorithms.Vir: Theoretical computer science. - ISSN 0304-3975 (Vol. 705, 2018, str. 75-83)Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasleLeto - 2018Jezik - angleškiCOBISS.SI-ID - 18180441
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 |
---|---|
Chiarelli, Nina | 35452 |
Hartinger, Tatiana Romina, 1987- | 36761 |
Johnson, Matthew | |
Milanič, Martin, 1980- | 30211 |
Paulusma, Daniël |
Vir: Osebne bibliografije
in: SICRIS
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Naslov za dostavo:
Med podatki člana manjka naslov.
Storitev za pridobivanje naslova trenutno ni dostopna, prosimo, poskusite še enkrat.
S klikom na gumb "V redu" boste potrdili zgoraj izbrano prevzemno mesto in dokončali postopek rezervacije.
S klikom na gumb "V redu" boste potrdili zgoraj izbrano prevzemno mesto in naslov za dostavo ter dokončali postopek rezervacije.
S klikom na gumb "V redu" boste potrdili zgoraj izbrani naslov za dostavo in dokončali postopek rezervacije.
Obvestilo
Trenutno je storitev za avtomatsko prijavo in rezervacijo nedostopna. Gradivo lahko rezervirate sami na portalu Biblos ali ponovno poskusite tukaj kasneje.
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Gradivo iz matične enote je brezplačno. Če je gradivo na mesto prevzema dostavljeno iz drugih enot, lahko knjižnica to storitev zaračuna.
Mesto prevzema | Status gradiva | Rezervacija |
---|
Rezervacija v teku
Prosimo, počakajte trenutek.
Rezervacija je uspela.
Rezervacija ni uspela.
Rezervacija...
Članska izkaznica:
Mesto prevzema: