Temat: stable graph - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: (H,k) stable graphs with minimum size
Autorzy:: Dudek, Aneta
Szymański, Artur
Zwonek, Małgorzata
Powiązania:: https://bibliotekanauki.pl/articles/743537.pdf
Data publikacji:: 2008
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: graph
stable graph
Opis:: Let us call a G (H,k) graph vertex stable if it contains a subgraph H ever after removing any of its k vertices. By Q(H,k) we will denote the minimum size of an (H,k) vertex stable graph. In this paper, we are interested in finding Q(₃,k), Q(₄,k), $Q(K_{1,p},k)$ and Q(Kₛ,k).
Źródło:: Discussiones Mathematicae Graph Theory; 2008, 28, 1; 137-149
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: (H,k) stable bipartite graphs with minimum size
Autorzy:: Dudek, Aneta
Zwonek, Małgorzata
Powiązania:: https://bibliotekanauki.pl/articles/744467.pdf
Data publikacji:: 2009
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: graph
vertex stable graph
Opis:: Let us call a graph G(H;k) vertex stable if it contains a subgraph H after removing any of its k vertices. In this paper we are interested in finding the $(K_{n,n+1};1)$ (respectively $(K_{n,n};1)$) vertex stable graphs with minimum size.
Źródło:: Discussiones Mathematicae Graph Theory; 2009, 29, 3; 573-581
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: On vertex stability with regard to complete bipartite subgraphs
Autorzy:: Dudek, Aneta
Żak, Andrzej
Powiązania:: https://bibliotekanauki.pl/articles/744100.pdf
Data publikacji:: 2010
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: vertex stable
bipartite graph
minimal size
Opis:: A graph G is called (H;k)-vertex stable if G contains a subgraph isomorphic to H ever after removing any of its k vertices. Q(H;k) denotes the minimum size among the sizes of all (H;k)-vertex stable graphs. In this paper we complete the characterization of $(K_{m,n};1)$-vertex stable graphs with minimum size. Namely, we prove that for m ≥ 2 and n ≥ m+2, $Q(K_{m,n};1) = mn+m+n$ and $K_{m,n}*K₁$ as well as $K_{m+1,n+1} - e$ are the only $(K_{m,n};1)$-vertex stable graphs with minimum size, confirming the conjecture of Dudek and Zwonek.
Źródło:: Discussiones Mathematicae Graph Theory; 2010, 30, 4; 663-669
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 4.

Tytuł:: Stable sets for $(P₆,K_{2,3})$-free graphs
Autorzy:: Mosca, Raffaele
Powiązania:: https://bibliotekanauki.pl/articles/743743.pdf
Data publikacji:: 2012
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: graph algorithms
stable sets
P₆-free graphs
Opis:: The Maximum Stable Set (MS) problem is a well known NP-hard problem. However different graph classes for which MS can be efficiently solved have been detected and the augmenting graph technique seems to be a fruitful tool to this aim. In this paper we apply a recent characterization of minimal augmenting graphs [22] to prove that MS can be solved for $(P₆,K_{2,3})$-free graphs in polynomial time, extending some known results.
Źródło:: Discussiones Mathematicae Graph Theory; 2012, 32, 3; 387-401
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 5.

Tytuł:: Extending the MAX Algorithm for Maximum Independent Set
Autorzy:: Lê, Ngoc C.
Brause, Christoph
Schiermeyer, Ingo
Powiązania:: https://bibliotekanauki.pl/articles/31339469.pdf
Data publikacji:: 2015-05-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: maximum independent set
stable set
stability number
independence number
reduction
graph transformation
MAX Algorithm
MIN Algorithm
Vertex Order Algorithm
Opis:: The maximum independent set problem is an NP-hard problem. In this paper, we consider Algorithm MAX, which is a polynomial time algorithm for finding a maximal independent set in a graph G. We present a set of forbidden induced subgraphs such that Algorithm MAX always results in finding a maximum independent set of G. We also describe two modifications of Algorithm MAX and sets of forbidden induced subgraphs for the new algorithms.
Źródło:: Discussiones Mathematicae Graph Theory; 2015, 35, 2; 365-386
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja