Search

Your search keyword '"Rybarczyk, Katarzyna"' showing total 42 results
Start Over Author "Rybarczyk, Katarzyna"
42 results on '"Rybarczyk, Katarzyna"'

1. The cover time of a sparse random intersection graph

Author

Bloznelis, Mindaugas, Jaworski, Jerzy, and Rybarczyk, Katarzyna

Subjects
Mathematics - Combinatorics, Mathematics - Probability, 05C81, 05C80, 05C82, 91D30
Abstract

Many known networks have structure of affiliation networks, where each of $n$ network's nodes (actors) selects an attribute set from a given collection of $m$ attributes and two nodes (actors) establish adjacency relation whenever they share a common attribute. We study behaviour of the random walk on such networks. For that purpose we use commonly used model of such networks -- random intersection graph. We establish the cover time of the simple random walk on the binomial random intersection graph ${\cal G}(n,m,p)$ at the connectivity threshold and above it. We consider the range of $n,m,p$ where the typical attribute is shared by (stochastically) bounded number of actors.

Published
2019

2. Finding Hamilton cycles in random intersection graphs

Author

Rybarczyk, Katarzyna

Subjects
Mathematics - Combinatorics, 05C80, 05C85
Abstract

The construction of the random intersection graph model is based on a random family of sets. Such structures, which are derived from intersections of sets, appear in a natural manner in many applications. In this article we study the problem of finding a Hamilton cycle in a random intersection graph. To this end we analyse a classical algorithm for finding Hamilton cycles in random graphs (algorithm HAM) and study its efficiency on graphs from a family of random intersection graphs (denoted here by G(n,m,p)). We prove that the threshold function for the property of HAM constructing a Hamilton cycle in G(n,m,p) is the same as the threshold function for the minimum degree at least two. Until now, known algorithms for finding Hamilton cycles in G(n,m,p) were designed to work in very small ranges of parameters and, unlike HAM, used the structure of the family of random sets.

Published
2017
Full Text
View/download PDF

3. A Note on the Conductance of the Binomial Random Intersection Graph

Author

Rybarczyk, Katarzyna, Bloznelis, Mindaugas, Jaworski, Jerzy, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Kamiński, Bogumił, editor, Prałat, Paweł, editor, and Szufel, Przemysław, editor

Published
2020
Full Text
View/download PDF

4. Poisson approximation of counts of subgraphs in random intersection graphs

Author

Rybarczyk, Katarzyna and Stark, Dudley

Subjects
Mathematics - Combinatorics, 05C80
Abstract

Random intersection graphs are characterized by three parameters: $n$, $m$ and $p$, where $n$ is the number of vertices, $m$ is the number of objects, and $p$ is the probability that a given object is associated with a given vertex. Two vertices in a random intersection graph are adjacent if and only if they have an associated object in common. When $m=\lfloor n^\alpha\rfloor$ for constant $\alpha$, we provide a condition, called {\em strictly $\alpha$-balanced}, for the Poisson convergence of the number of induced copies of a fixed subgraph., Comment: 17 pages, submitted version

Published
2016

5. Equivalence of the random intersection graph and G(n,p)

Author

Rybarczyk, Katarzyna

Subjects
Mathematics - Combinatorics, Mathematics - Probability, 05C80, 60C05
Abstract

We solve the conjecture posed by Fill, Scheinerman and Singer-Cohen and show the equivalence of the sharp threshold functions of the random intersection graph G(n,m,p) with $m >= n^3$ and a graph in which each edge appears independently. Moreover we prove sharper equivalence results under some additional assumptions.

Published
2009
Full Text
View/download PDF

6. Sharp threshold functions for the random intersection graph via coupling method?

Author

Rybarczyk, Katarzyna

Subjects
Mathematics - Combinatorics, 05C80, 60C05
Abstract

We will present a new method, which enables us to find threshold functions for many properties in random intersection graphs. This method will be used to establish sharp threshold functions in random intersection graphs for k-connectivity, perfect matching containment and Hamilton cycle containment.

Published
2009

7. Recent Progress in Complex Network Analysis: Properties of Random Intersection Graphs

Author

Bloznelis, Mindaugas, Godehardt, Erhard, Jaworski, Jerzy, Kurauskas, Valentas, Rybarczyk, Katarzyna, Bock, Hans-Hermann, Editor-in-chief, Gaul, Wolfgang, Editor-in-chief, Baier, Daniel, Series editor, Vichi, Maurizio, Editor-in-chief, Critchley, Frank, Series editor, Decker, Reinhold, Series editor, Diday, Edwin, Series editor, Greenacre, Michael, Series editor, Lauro, Carlo Natale, Series editor, Meulman, Jacqueline, Series editor, Monari, Paola, Series editor, Nishisato, Shizuhiko, Series editor, Ohsumi, Noboru, Series editor, Opitz, Otto, Series editor, Ritter, Gunter, Series editor, Schader, Martin, Series editor, Weihs, Claus, Editor-in-chief, Lausen, Berthold, editor, Krolak-Schwerdt, Sabine, editor, and Böhmer, Matthias, editor

Published
2015
Full Text
View/download PDF

8. Recent Progress in Complex Network Analysis: Models of Random Intersection Graphs

Author

Bloznelis, Mindaugas, Godehardt, Erhard, Jaworski, Jerzy, Kurauskas, Valentas, Rybarczyk, Katarzyna, Bock, Hans-Hermann, Editor-in-chief, Gaul, Wolfgang, Editor-in-chief, Baier, Daniel, Series editor, Vichi, Maurizio, Editor-in-chief, Critchley, Frank, Series editor, Decker, Reinhold, Series editor, Diday, Edwin, Series editor, Greenacre, Michael, Series editor, Lauro, Carlo Natale, Series editor, Meulman, Jacqueline, Series editor, Monari, Paola, Series editor, Nishisato, Shizuhiko, Series editor, Ohsumi, Noboru, Series editor, Opitz, Otto, Series editor, Ritter, Gunter, Series editor, Schader, Martin, Series editor, Weihs, Claus, Editor-in-chief, Lausen, Berthold, editor, Krolak-Schwerdt, Sabine, editor, and Böhmer, Matthias, editor

Published
2015
Full Text
View/download PDF

9. The Chromatic Number of Random Intersection Graphs

Author

Rybarczyk Katarzyna

Subjects
random intersection graphs, chromatic number, colouring algorithms, Mathematics, QA1-939
Abstract

We study problems related to the chromatic number of a random intersection graph G (n,m, p). We introduce two new algorithms which colour G (n,m, p) with almost optimum number of colours with probability tending to 1 as n → ∞. Moreover we find a range of parameters for which the chromatic number of G (n,m, p) asymptotically equals its clique number.

Published
2017
Full Text
View/download PDF

18. Forward-Secure Key Evolution in Wireless Sensor Networks

Author

Klonowski, Marek, Kutyłowski, Mirosław, Ren, Michał, Rybarczyk, Katarzyna, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Bao, Feng, editor, Ling, San, editor, Okamoto, Tatsuaki, editor, Wang, Huaxiong, editor, and Xing, Chaoping, editor

Published
2007
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results