Wyszukiwarka
Nie znaleźliśmy wyników w zadanych kryteriach!
Ale mamy wyniki w innych katalogach.Filtry
wszystkich: 69
Wyniki wyszukiwania dla: INDEPPENDENCE
-
The Potential of Greed for Independence
PublikacjaThe well-known lower bound on the independence number of a graph due to Caro and Wei can be established as a performance guarantee of two natural and simple greedy algorithms or of a simple randomized algorithm. We study possible generalizations and improvements of these approaches using vertex weights and discuss conditions on so-called potential functions p(G) : V(G) -> N_0 defined on the vertex set of a graph G for which suitably...
-
Common Independence in Graphs
PublikacjaAbstract: The cardinality of a largest independent set of G, denoted by α(G), is called the independence number of G. The independent domination number i(G) of a graph G is the cardinality of a smallest independent dominating set of G. We introduce the concept of the common independence number of a graph G, denoted by αc(G), as the greatest integer r such that every vertex of G belongs to some independent subset X of VG with |X|...
-
Bridges to Independence / Mosty ku niepodległości
Publikacja -
Independence in uniform linear triangle-free hypergraphs
PublikacjaThe independence number a(H) of a hypergraph H is the maximum cardinality of a set of vertices of H that does not contain an edge of H. Generalizing Shearer’s classical lower bound on the independence number of triangle-free graphs Shearer (1991), and considerably improving recent results of Li and Zang (2006) and Chishti et al. (2014), we show a new lower bound for a(H) for an r-uniform linear triangle-free hypergraph H with r>=2.
-
New potential functions for greedy independence and coloring
PublikacjaA potential function $f_G$ of a finite, simple and undirected graph $G=(V,E)$ is an arbitrary function $f_G : V(G) \rightarrow \mathbb{N}_0$ that assigns a nonnegative integer to every vertex of a graph $G$. In this paper we define the iterative process of computing the step potential function $q_G$ such that $q_G(v)\leq d_G(v)$ for all $v\in V(G)$. We use this function in the development of new Caro-Wei-type and Brooks-type...
-
On the independence number of some strong products of cycle-powers
PublikacjaIn the paper we give some theoretical and computational results on the third strong power of cycle-powers, for example, we have found the independence numbers alpha((C^2_10)^⊠3) = 30 and alpha((C^4 _14)^⊠3) = 14. A number of optimizations have been introduced to improve the running time of our exhaustive algorithm used to establish the independence number of the third strong power of cycle-powers. Moreover, our results establish...
-
Endoscopy video analysis algorithms and their independence of rotation , brightness , contrast , color and blur
PublikacjaThe article presents selected image analysis algorithms for endoscopy videos. Mathematical methods that are part of these algorithms are described, and authors’ claims about the characteristics of these algorithms, such as the independence of rotation, brightness, contrast, etc. are mentioned. Using the common test on the real endoscopic image database and a set of image transformations, the validity of these claims was checked...
-
Duration of disability, functional independence, coping styles and the quality of life in patients with spinal cord injury – Pilot study
Publikacja -
1st Academic Conference "Areas of Finnish Studies: Language, Culture and Nation", organised on the occasion of the centenary of Finnish independence (Gdańsk, 15-16 May 2017)
Publikacja -
Graphs hard-to-process for greedy algorithm MIN
PublikacjaWe compare results of selected algorithms that approximate the independence number in terms of the quality of constructed solutions. Furthermore, we establish smallest hard- to-process graphs for the greedy algorithm MIN.