Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "vertex cover" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-9 z 9
    Tytuł:
    An Efficient Polynomial Time Approximation Scheme for the Vertex Cover P3 Problem on Planar Graphs
    Autorzy:
    Tu, Jianhua
    Shi, Yongtang
    Powiązania:
    https://bibliotekanauki.pl/articles/31343724.pdf
    Data publikacji:
    2019-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    combinatorial optimization
    vertex cover P3 problem
    branch- width
    planar graphs
    EPTAS
    Opis:
    Given a graph G = (V,E), the task in the vertex cover P3(VCP3) problem is to find a minimum subset of vertices F ⊆ V such that every path of order 3 in G contains at least one vertex from F. The VCP3 problem remains NP-hard even in planar graphs and has many applications in real world. In this paper, we give a dynamic-programming algorithm to solve the VCP3 problem on graphs of bounded branchwidth. Using the dynamic programming algorithm and the Baker’s EPTAS framework for NP-hard problems, we present an efficient polynomial time approximation scheme (EPTAS) for the VCP3 problem on planar graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2019, 39, 1; 55-65
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On Generalized Sierpiński Graphs
    Autorzy:
    Rodríguez-Velázquez, Juan Alberto
    Rodríguez-Bazan, Erick David
    Estrada-Moreno, Alejandro
    Powiązania:
    https://bibliotekanauki.pl/articles/31341732.pdf
    Data publikacji:
    2017-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    Sierpiński graphs
    vertex cover number
    independence number
    chromatic number
    domination number
    Opis:
    In this paper we obtain closed formulae for several parameters of generalized Sierpiński graphs S(G, t) in terms of parameters of the base graph G. In particular, we focus on the chromatic, vertex cover, clique and domination numbers.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 3; 547-560
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A Constructive Characterization of Vertex Cover Roman Trees
    Autorzy:
    Martínez, Abel Cabrera
    Kuziak, Dorota
    Yero, Ismael G.
    Powiązania:
    https://bibliotekanauki.pl/articles/32083833.pdf
    Data publikacji:
    2021-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    Roman domination
    outer-independent Roman domination
    vertex cover
    vertex independence
    trees
    Opis:
    A Roman dominating function on a graph G = (V(G), E(G)) is a function f : V(G) → {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The Roman dominating function f is an outer-independent Roman dominating function on G if the set of vertices labeled with zero under f is an independent set. The outer-independent Roman domination number γoiR(G) is the minimum weight w(f) = Σv∈V(G)f(v) of any outer-independent Roman dominating function f of G. A vertex cover of a graph G is a set of vertices that covers all the edges of G. The minimum cardinality of a vertex cover is denoted by α(G). A graph G is a vertex cover Roman graph if γoiR(G) = 2α(G). A constructive characterization of the vertex cover Roman trees is given in this article.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 1; 267-283
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Dominating Vertex Covers: The Vertex-Edge Domination Problem
    Autorzy:
    Klostermeyer, William F.
    Messinger, Margaret-Ellen
    Yeo, Anders
    Powiązania:
    https://bibliotekanauki.pl/articles/32083812.pdf
    Data publikacji:
    2021-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    cubic graph
    dominating set
    vertex cover
    vertex-edge dominating set
    Opis:
    The vertex-edge domination number of a graph, γve(G), is defined to be the cardinality of a smallest set D such that there exists a vertex cover C of G such that each vertex in C is dominated by a vertex in D. This is motivated by the problem of determining how many guards are needed in a graph so that a searchlight can be shone down each edge by a guard either incident to that edge or at most distance one from a vertex incident to the edge. Our main result is that for any cubic graph G with n vertices, γve(G) ≤ 9n/26. We also show that it is NP-hard to decide if γve(G) = γ(G) for bipartite graph G.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 1; 123-132
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A new and fast approximation algorithm for vertex cover using a maximum independent set (VCUMI)
    Autorzy:
    Khan, I.
    Riaz, N.
    Powiązania:
    https://bibliotekanauki.pl/articles/406436.pdf
    Data publikacji:
    2015
    Wydawca:
    Politechnika Wrocławska. Oficyna Wydawnicza Politechniki Wrocławskiej
    Tematy:
    non-deterministic polynomial
    vertex cover
    independent set
    benchmark
    error ratio
    Opis:
    The importance of non-deterministic polynomial (NP) problems in real world scenarios has compelled researchers to consider simple ways of finding approximate solutions to these problems in polynomial time. Minimum vertex cover is an NP complete problem, where the objective is to cover all the edges in a graph with the minimal number of vertices possible. The maximal independent set and maximal clique problems also belong to the same class. An important property that we have analyzed while considering various approaches to find approximate solutions to the minimum vertex cover problem (MVC) is that solving MVC directly can result in a bigger error ratio. We propose a new approximation algorithm for the minimum vertex cover problem called vertex cover using a maximum independent set (VCUMI). This algorithm works by removing the nodes of a maximum independent set until the graph is an approximate solution of MVC. Based on empirical results, it can be stated that VCUMI outperforms all competing algorithms presented in the literature. Based on all the benchmarks used, VCUMI achieved the worst case error ratio of 1.033, while VSA, MDG and NOVAC-1 gave the worst error ratios of 1.583, 1.107 and 1.04, respectively.
    Źródło:
    Operations Research and Decisions; 2015, 25, 4; 5-18
    2081-8858
    2391-6060
    Pojawia się w:
    Operations Research and Decisions
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Edge Dominating Sets and Vertex Covers
    Autorzy:
    Dutton, Ronald
    Klostermeyer, William F.
    Powiązania:
    https://bibliotekanauki.pl/articles/30146532.pdf
    Data publikacji:
    2013-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge dominating set
    matching
    total dominating set
    vertex cover
    Opis:
    Bipartite graphs with equal edge domination number and maximum matching cardinality are characterized. These two parameters are used to develop bounds on the vertex cover and total vertex cover numbers of graphs and a resulting chain of vertex covering, edge domination, and matching parameters is explored. In addition, the total vertex cover number is compared to the total domination number of trees and grid graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 2; 437-456
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Some Variations of Perfect Graphs
    Autorzy:
    Dettlaff, Magda
    Lemańska, Magdalena
    Semanišin, Gabriel
    Zuazua, Rita
    Powiązania:
    https://bibliotekanauki.pl/articles/31340821.pdf
    Data publikacji:
    2016-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    k-path vertex cover
    distance k-domination number
    perfect graphs
    Opis:
    We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) = γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k-path vertex cover number and the distance (k − 1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k ≥ 2. Moreover, we provide a complete characterisation of (ψ2 − γ1)- perfect graphs describing the set of its forbidden induced subgraphs and providing the explicit characterisation of the structure of graphs belonging to this family.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2016, 36, 3; 661-668
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Remarks on Dynamic Monopolies with Given Average Thresholds
    Autorzy:
    Centeno, Carmen C.
    Rautenbach, Dieter
    Powiązania:
    https://bibliotekanauki.pl/articles/31339133.pdf
    Data publikacji:
    2015-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    dynamic monopoly
    degenerate set
    vertex cover
    independent set
    Opis:
    Dynamic monopolies in graphs have been studied as a model for spreading processes within networks. Together with their dual notion, the generalized degenerate sets, they form the immediate generalization of the classical notions of vertex covers and independent sets in a graph. We present results concerning dynamic monopolies in graphs of given average threshold values extending and generalizing previous results of Khoshkhah et al. [On dynamic monopolies of graphs: The average and strict majority thresholds, Discrete Optimization 9 (2012) 77-83] and Zaker [Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs, Discrete Appl. Math. 161 (2013) 2716-2723].
    Źródło:
    Discussiones Mathematicae Graph Theory; 2015, 35, 1; 133-140
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On the Path Sequence of a Graph
    Autorzy:
    Bakalarski, Sławomir
    Zygadło, Jakub
    Powiązania:
    https://bibliotekanauki.pl/articles/1373669.pdf
    Data publikacji:
    2015
    Wydawca:
    Uniwersytet Jagielloński. Wydawnictwo Uniwersytetu Jagiellońskiego
    Tematy:
    $k$-path vertex cover
    path sequence
    list for small graphs
    Opis:
    A subset S of vertices of a graph $G = (V, E)$ is called a $k$-path vertex cover if every path on $k$ vertices in $G$ contains at least one vertex from $S$. Denote by $psi_k(G)$ the minimum cardinality of a $k$-path vertex cover in $G$ and form a sequence $\psi(G) = (\psi_1 (G), \psi_2 (G), . . . , \psi_{|V|} (G))$, called the path sequence of $G$. In this paper we prove necessary and sufficient conditions for two integers to appear on fixed positions in $\psi(G)$. A complete list of all possible path sequences (with multiplicities) for small connected graphs is also given.
    Źródło:
    Schedae Informaticae; 2015, 24; 239-251
    0860-0295
    2083-8476
    Pojawia się w:
    Schedae Informaticae
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-9 z 9

      Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies