Filtry
wszystkich: 2153
-
Katalog
- Publikacje 1645 wyników po odfiltrowaniu
- Czasopisma 46 wyników po odfiltrowaniu
- Konferencje 35 wyników po odfiltrowaniu
- Osoby 65 wyników po odfiltrowaniu
- Wynalazki 1 wyników po odfiltrowaniu
- Projekty 7 wyników po odfiltrowaniu
- Kursy Online 51 wyników po odfiltrowaniu
- Wydarzenia 10 wyników po odfiltrowaniu
- Dane Badawcze 293 wyników po odfiltrowaniu
wyświetlamy 1000 najlepszych wyników Pomoc
Wyniki wyszukiwania dla: RANDOM GRAPHS
-
On extremal sizes of locally k-tree graphs
PublikacjaA graph G is a locally k-tree graph if for any vertex v the subgraph induced by the neighbours of v is a k-tree, k>=0, where 0-tree is an edgeless graph, 1-tree is a tree. We characterize the minimum-size locally k-trees with n vertices. The minimum-size connected locally k-trees are simply (k + 1)-trees. For k >= 1, we construct locally k-trees which are maximal with respect to the spanning subgraph relation. Consequently, the...
-
Sum Coloring of Bipartite Graphs with Bounded Degree
Publikacja -
Sum coloring of bipartite graphs with bounded degree.
PublikacjaArtykuł poświęcony jest złożoności obliczeniowej zagadnienia sumacyjnego kolorowania grafów dwudzielnych o ograniczonym stopniu. Zawiera dowód tego, że sumacyjne kolorowanie grafów dwudzielnych stopnia mniejszego równego 5 jest NP-zupełne oraz opis wielomianowego algorytmu, który optymalnie sumacyjnie koloruje grafy dwudzielne podkubiczne.
-
Cholesky factorization of matrices in parallel and ranking of graphs.
PublikacjaUporządkowane kolorowanie znajduje zastosowanie przy równoległej faktoryzacji macierzy metodą Cholesky'ego. Praca zawiera opis tego zastosowania. Podano także algorytmy optymalnego uporządkowanego kolorowania krawędzi pewnych klas grafów: grafów pełnych dwudzielnych oraz powstałych z pełnych dwudzielnych przez usunięcie O(log n) krawędzi.
-
Domination-Related Parameters in Rooted Product Graphs
PublikacjaAbstract A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those sets of vertices of a graph satisfying some domination property together with other conditions on the vertices of G. Here, we investigate several domination-related parameters in rooted product graphs.
-
Graphs with convex domination number close to their order
PublikacjaW pracy opisane są grafy z liczbą dominowania wypukłego bliską ilości ich wierzchołków.
-
Self-stabilizing algorithm for edge-coloring of graphs
PublikacjaReferat ten poświęcony jest kolorowaniu grafów w modelu rozproszonym.Podano samostabilizujący się algorytm kolorowania krawędzi grafu wraz z dowodem poprawności oraz oszacowaniem jego czasu działania.
-
On bipartization of cubic graphs by removal of an independent set
PublikacjaWe study a new problem for cubic graphs: bipartization of a cubic graph Q by deleting sufficiently large independent set.
-
Towards Increasing Density of Relations in Category Graphs
PublikacjaIn the chapter we propose methods for identifying new associations between Wikipedia categories. The first method is based on Bag-of-Words (BOW) representation of Wikipedia articles. Using similarity of the articles belonging to different categories allows to calculate the information about categories similarity. The second method is based on average scores given to categories while categorizing documents by our dedicated score-based...
-
Bipartite theory of graphs: outer-independent domination
PublikacjaLet $G = (V,E)$ be a bipartite graph with partite sets $X$ and $Y$. Two vertices of $X$ are $X$-adjacent if they have a common neighbor in $Y$, and they are $X$-independent otherwise. A subset $D \subseteq X$ is an $X$-outer-independent dominating set of $G$ if every vertex of $X \setminus D$ has an $X$-neighbor in $D$, and all vertices of $X \setminus D$ are pairwise $X$-independent. The $X$-outer-independent domination number...
-
Minimum order of graphs with given coloring parameters
PublikacjaA complete k-coloring of a graph G=(V,E) is an assignment F: V -> {1,...,k} of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively investigated graph invariants related to complete colorings are the minimum and maximum number of colors in a complete coloring (chromatic number χ(G) and achromatic number ψ(G), respectively),...
-
Parallel query processing and edge ranking of graphs
PublikacjaArtykuł poświęcony jest problemowi szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym. Jednym z zastosowań jest poszukiwanie optymalnych harmonogramów w równoległym przetwarzaniu zapytań w relacyjnych bazach danych. Podajemy nowe oszacowanie funkcji dobroci przybliżonego algorytmu autorstwa Makino, Uno i Ibaraki wraz z rezultatami testów komputerowych przeprowadzonych dla grafów losowych.
-
On the size of identifying codes in triangle-free graphs
PublikacjaIn an undirected graph G, a subset C⊆V(G) such that C is a dominating set of G, and each vertex in V(G) is dominated by a distinct subset of vertices from C, is called an identifying code of G. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. For a given identifiable graph G, let gammaID(G) be the minimum cardinality of an identifying code in G. In this paper, we show that for any connected...
-
Paired domination subdivision and multisubdivision numbers of graphs
PublikacjaThe paired domination subdivision number sdpr(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the paired domination number of G. We prove that the decision problem of the paired domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the paired domination muttisubdivision number of a nonempty graph...
-
Decontaminating Arbitrary Graphs by Mobile Agents: a Survey
PublikacjaA team of mobile agents starting from homebases need to visit and clean all nodes of the network. The goal is to find a strategy, which would be optimal in the sense of the number of needed entities, the number of moves performed by them or the completion time of the strategy. Currently, the field of distributed graph searching by a team of mobile agents is rapidly expanding and many new approaches and models are being presented...
-
Total Domination Versus Domination in Cubic Graphs
PublikacjaA dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number,γ(G), and total domination number, γ_t(G), are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, \Gamma(G), and the upper total domination...
-
Progress on Roman and Weakly Connected Roman Graphs
PublikacjaA graph G for which γR(G)=2γ(G) is the Roman graph, and if γwcR(G)=2γwc(G), then G is the weakly connected Roman graph. In this paper, we show that the decision problem of whether a bipartite graph is Roman is a co-NP-hard problem. Next, we prove similar results for weakly connected Roman graphs. We also study Roman trees improving the result of M.A. Henning’s A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002)....
-
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.
-
Graphs with equal domination and certified domination numbers
PublikacjaA setDof vertices of a graphG= (VG,EG) is a dominating set ofGif every vertexinVG−Dis adjacent to at least one vertex inD. The domination number (upper dominationnumber, respectively) ofG, denoted byγ(G) (Γ(G), respectively), is the cardinality ofa smallest (largest minimal, respectively) dominating set ofG. A subsetD⊆VGis calleda certified dominating set ofGifDis a dominating set ofGand every vertex inDhas eitherzero...
-
Domination subdivision and domination multisubdivision numbers of graphs
PublikacjaThe domination subdivision number sd(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number of G. It has been shown [10] that sd(T)<=3 for any tree T. We prove that the decision problem of the domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the domination multisubdivision number...
-
On the super domination number of lexicographic product graphs
PublikacjaThe neighbourhood of a vertexvof a graphGis the setN(v) of all verticesadjacent tovinG. ForD⊆V(G) we defineD=V(G)\D. A setD⊆V(G) is called a super dominating set if for every vertexu∈D, there existsv∈Dsuch thatN(v)∩D={u}. The super domination number ofGis theminimum cardinality among all super dominating sets inG. In this article weobtain closed formulas and tight bounds for the super dominating number oflexicographic product...
-
Chromatic cost coloring of weighted bipartite graphs
PublikacjaGiven a graph G and a sequence of color costs C, the Cost Coloring optimization problem consists in finding a coloring of G with the smallest total cost with respect to C. We present an analysis of this problem with respect to weighted bipartite graphs. We specify for which finite sequences of color costs the problem is NP-hard and we present an exact polynomial algorithm for the other finite sequences. These results are then extended...
-
Numerical simulation of threshold-crossing problem for random fields of environmental contamination
PublikacjaCelem artykułu jest analiza szacowania prawdopodobieństwa, że pole losowe zanieczyszczeń nie przekracza pewnej wartości w danej dwuwymiarowej przestrzeni. W analizie wykorzystano metodę modelowania stochastycznego wykorzystując procedurę symulacji warunkowej. Opisany przykład praktycznego zastosowania metody dotyczy pola zanieczyszczenia metalami ciężkimi gruntu w regionie gdańskim.
-
Numerical simulations of space-time conditional random fields of ground motions
PublikacjaArtykuł przedstawia metodę modelowania stochastycznego efektu propagacji fali sejsmicznej z wykorzystaniem przestrzenno-czasowej funkcji korelacji pola losowego trzęsienia ziemi. Metodę wykorzystano do generacji nieznanych historii czasowych trzęsienia w wybranych punktach na podstawie znanego rejestru w jednym miejscu. Wyniki pokazały, iż zastosowanie zaproponowanej metody prowadzi do relatywnie małych błędów symulacji.
-
Typing of Scopulariopsis and Microascus fungi by Random Amplified Polymorphic DNA (RAPD)
PublikacjaOBJECTIVES Scopulariopsis species and their teleomorphs of the genus Microascus are commonly isolated from soil, decaying plant material and indoor environments. Moreover, certain Scopulariopsis and Microascus species are recognised as opportunistic human pathogens. Although most species can be identified by detailed morphological study, phenotypic characters appear to overlap in several cases and morphology seems to be insufficient...
-
Conditional random field simulation of ground motions for large shell structures.
PublikacjaZaprezentowano metodę stochastycznego modelowania efektu propagacji fali trzęsienia ziemi i analizowano wpływ tego efektu na konstrukcje powłokowe znacznych rozmiarów. Symulowane przy użyciu tej metody rejestry trzęsień ziemi w wybranych punktach podporowych mogą być wykorzystane do analizy dynamicznej zachowania się konstrukcji. Przykładem analizowanej konstrukcji budowlanej jest zbiornik cylindryczny o średnicy 100 m.
-
A Robust Random Forest Model for Classifying the Severity of Partial Discharges in Dielectrics
PublikacjaPartial Discharges (PDs) are a common source of degradation in electrical assets. It is essential that the extent of the deterioration level of insulating medium is correctly identified, to optimize maintenance schedules and prevent abrupt power outages. Temporal PD signals received from damaged insulation, collected through the IEC-60270 method is the gold standard for PD detection. Temporal signals may be transformed to the frequency...
-
Computations of critical load value of composite shell with random geometric imperfections
PublikacjaThe work presents the numerical analysis of composite shell with geometric imperfections subjected to compression along its generatrix. The imperfections are described as single indentations and random fields with random parameters of shape and correlation. The fields are generated with the use of the authors made program. Using the authors’ FEM software as well as commercial package Femap with NX Nastran, the critical load values...
-
Oxide layers fabricated by spray pyrolysis for resistance random access memory
PublikacjaW pracy zbadano przydatność pirolizy aerozolowej do wytwarzania warstw dla memrystorów.
-
Implementation of constant component filter in measurements of random telegraph signal noise
PublikacjaNoise is generated in all semiconductor devices. The intensity of these fluctuations depends on used elements, manufacturing process, operating conditions and device type. The result noise is a superposition of different kinds of fluctuations like thermal noise, generation-recombination noise, 1/f noise, shot noise and Random Telegraph Signal (RTS) noise. The last one, RTS noise is observed as nonstationary impulse fluctuations....
-
Generation of random fields to reflect material and geometric imperfections of plates and shells
PublikacjaThe paper covers two patterns of random field generation: conditional acceptance – rejection method and Karhunen – Loève expansion. The generation of two-dimensional random fields is essential in plates and shells analysis, allowing for a relevant limit and critical state assessment of geometrically and ma-terially imperfect structures. The features of both generation methods dedicate them to selected problems.
-
Complementarity between entanglement-assisted and quantum distributed random access code
PublikacjaCollaborative communication tasks such as random access codes (RACs) employing quantum resources have manifested great potential in enhancing information processing capabilities beyond the classical limitations. The two quantum variants of RACs, namely, quantum random access code (QRAC) and the entanglement-assisted random access code (EARAC), have demonstrated equal prowess for a number of tasks. However, there do exist specific...
-
Connections between Mutually Unbiased Bases and Quantum Random Access Codes
PublikacjaWe present a new quantum communication complexity protocol, the promise--Quantum Random Access Code, which allows us to introduce a new measure of unbiasedness for bases of Hilbert spaces. The proposed measure possesses a clear operational meaning and can be used to investigate whether a specific number of mutually unbiased bases exist in a given dimension by employing Semi--Definite Programming techniques.
-
Probabilistic Analysis of Structure Models using Target Random Sampling (TRS)
PublikacjaThe work presents testing methods of sensitivity and reliability of mechanical or structural systems. All computations concerned the case of Zigler column, a simple model of a compressed column involving two random variables only. A conclusion was drawn that the standard Monte Carlo method, its reduction variants and the response surface method allow to assess the sensitivity of structural response to the variation of random structural...
-
EvOLAP Graph – Evolution and OLAP-Aware Graph Data Model
PublikacjaThe objective of this paper is to propose a graph model that would be suitable for providing OLAP features on graph databases. The included features allow for a multidimensional and multilevel view on data and support analytical queries on operational and historical graph data. In contrast to many existing approaches tailored for static graphs, the paper addresses the issue for the changing graph schema. The model, named Evolution...
-
Dataset of non-isomorphic graphs of the coloring types (K3,Km;n), 2<m<7, 1<n<R(3,m)
Dane BadawczeFor K3 and Km graphs, a coloring type (K3,Km;n) is such an edge coloring of the full Kn graph, which does not have the K3 subgraph in the first color (representing by no edges in the graph) or the Km subgraph in the second color (representing by edges in the graph).The Ramsey number R(3,m) is the smallest natural number n such that for any edge coloring...
-
Dataset of non-isomorphic graphs being coloring types (K5-e,Km-e;n), 2<m<5, 1<n<R(K5-e,Km-e)
Dane BadawczeFor K5-e and Km-e graphs, the type coloring (K5-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K5-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K5-e,Km-e) is the smallest...
-
Dataset of non-isomorphic graphs being coloring types (K6-e,Km-e;n), 2<m<5, 1<n<R(K6-e,Km-e)
Dane BadawczeFor K6-e and Km-e graphs, the type coloring (K6-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K6-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed. The Ramsey number R(K6-e,Km-e) is the smallest...
-
Dataset of non-isomorphic graphs of the coloring types (K4,Km-e;n), 2<m<5, 1<n<R(K4,Km-e)
Dane BadawczeFor K4 and Km-e graphs, a coloring type (K4,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K4 subgraph in the first color (representing by no edges in the graph) or the Km-e subgraph in the second color (representing by edges in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K4,Km-e)...
-
Dataset of non-isomorphic graphs of the coloring types (K4,K4;n), 1<n<R(4,4)
Dane BadawczeFor K4 graph, a coloring type (K4,K4;n) is such an edge coloring of the full Kn graph, which does not have the K4 subgraph in the first color (representing by no edges in the graph) or the K4 subgraph in the second color (representing by edges in the graph).The Ramsey number R(4,4) is the smallest natural number n such that for any edge coloring of...
-
Dataset of non-isomorphic graphs of the coloring types (Km,K3-e;n), 4<m<8, 1<n<R(Km,K3-e)
Dane BadawczeFor Km and K3-e graphs, a coloring type (Km,K3-e;n) is such an edge coloring of the full Kn graph, which does not have the Km subgraph in the first color (representing by no edges in the graph) or the K3-e subgraph in the second color (representing by edges in the graph). K3-e means the full Km graph with one edge removed.The Ramsey number R(Km,K3-e)...
-
Dataset of non-isomorphic graphs of the coloring types (K3,Km-e;n), 2<m<7, 1<n<R(K3,Km-e).
Dane BadawczeFor K3 and Km-e graphs, a coloring type (K3,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K3 subgraph in the first color (representing by no edges in the graph) or the Km-e subgraph in the second color (representing by edges in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K3,Km-e)...
-
A note on the strength and minimum color sum of bipartite graphs
PublikacjaSiłą grafu G nazywamy najmniejszą liczbę całkowitą s, taką że istniej pokolorowanie grafu G, o minimalnej sumie przy użyciu kolorów {1,...,s}. W pracy pokazano, że w grafach dwudzielnych stopnia D zachodzi oszacowanie s <= ceil(D/2) + 1. Z obserwacji tej wynika algorytm wielomianowy do obliczania siły i sumy chromatycznej w grafach dwudzielnych stopnia co najwyżej 4.
-
The maximum edge-disjoint paths problem in complete graphs
PublikacjaRozważono problem ścieżek krawędziowo rozłącznych w grafach pełnych. Zaproponowano wielomianowe algorytmy: 3.75-przybliżony (off-line) oraz 6.47-przybliżony (on-line), poprawiając tym samym wyniki wcześniej znane z literatury [P. Carmi, T. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, in: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, in: LNCS, vol. 2880, 2003, pp. 143-155]. Ponadto...
-
A note on compact and compact circular edge-colorings of graphs
PublikacjaW pracy rozważamy dwa warianty kolorowania krawędzi grafów prostych i ważonych, mianowicie kolorowania zwarte oraz zwarte cyrkularne. Rozważamy relacje pomiędzy nimi. Dowodzimy, że każdy zewnętrznie planarny graf dwudzielny posiada zwarte pokolorowanie krawędziowe oraz, że problem ten dla grafów ogólnych jest NP-zupełny. Podajemy również wielomianowy 1.5-przybliżony algorytm oraz pseudowielomianowy dokładny algorytm zwartego cyrkularnego...
-
Early detection of imminent threats in social relation graphs
PublikacjaWczesne wykrywanie zagrożeń i anomalii w sieciach społecznych jest dziś prawdziwym wyzwaniem. Ludzie w realnym świecie tworzą wiele złożonych relacji społecznych, które mogą być przedstawione za pomocą grafów, w których węzły reprezentują aktorów (pojedyncze osoby lub organizacje) a krawędzie wskazują na powiązania pomiędzy nimi. Analiza nieustannie zmieniających się relacji pomiędzy aktorami może wskazać konkretne nadciągające...
-
The circular chromatic index of some class 2 graphs
PublikacjaW artykule został wyznaczony cyrkularny indeks chromatyczny dla dwóch rodzin grafów klasy 2. Co więcej, podano nie trywialne oszacowania tego parametru dla snarków Isaacsa i Goldberga. Na koniec artykułu rozważana jest złożoność obliczeniowa problemów związanych z cyrkularnym kolorowaniem krawędzi.
-
The complexity of the T-coloring problem for graphs with small degree
Publikacja -
Some results concerning the complexity of restricted colorings of graphs
Publikacja -
Edge-chromatic sum of trees and bounded cyclicity graphs
Publikacja