Výsledky vyhledávání

Independent transversals versus transversals

Autor: Dabrowski, K. K., Johnson, M., Paesani, G., Daniel Paulusma, Zamaraev, V.

Publikováno v: Acta Mathematica Universitatis Comenianae
Scopus-Elsevier

We compare the minimum size of a vertex cover, feedback vertex set and odd cycle transversal of a graph with the minimum size of the corresponding variants in which the transversal must be an independent set. We investigate for which graphs H the two

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::368bd8e5a9a7f2518aff2937a68ba2c2
http://livrepository.liverpool.ac.uk/3092259/1/paper44.pdf

Zobrazit plný text záznamu

Akademický článek

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Connected vertex cover for (sP1+P5)-free graphs

Autor: Johnson, M., Paesani, G., Paulusma, D.

Publikováno v: Brandstädt, Andreas & Köhler, Ekkehard & Meer, Klaus (Eds.). (2018). Graph-theoretic concepts in computer science : 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings. Cham: Springer, pp. 279-291, Lecture notes in computer science(11159)

The Connected Vertex Cover problem is to decide if a graph G has a vertex cover of size at most k that induces a connected subgraph of G. This is a well-studied problem, known to be NP-complete for restricted graph classes, and, in particular, for H-

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=od_______328::f1d5bc05c074512463419eed26cb117b
http://dro.dur.ac.uk/25710/1/25710.pdf

Zobrazit plný text záznamu

On the Price of Independence for Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal

Autor: Dabrowski, K.K., Johnson, M., Paesani, G., Paulusma, D., Zamaraev, V.

Publikováno v: Potapov, Igor & Spirakis, Paul & Worrell, James (Eds.). (2018). 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 63:1-63:15, Leibniz International Proceedings in Informatics(117)

Let $vc(G)$, $fvs(G)$ and $oct(G)$, respectively, denote the size of a minimum vertex cover, minimum feedback vertex set and minimum odd cycle transversal in a graph $G$. One can ask, when looking for these sets in a graph, how much bigger might they

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::964f05a8cac653380450066e03c2073c

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání