The Experts below are selected from a list of 15033 Experts worldwide ranked by ideXlab platform
Mindaugas Bloznelis - One of the best experts on this subject based on the ideXlab platform.
-
degree degree distribution in a power law random Intersection Graph with clustering
arXiv: Probability, 2014Co-Authors: Mindaugas BloznelisAbstract:The bivariate distribution of degrees of adjacent vertices (degree-degree distribution) is an important network characteristic defining the statistical dependencies between degrees of adjacent vertices. We show the asymptotic degree-degree distribution of a sparse inhomogeneous random Intersection Graph and discuss its relation to the clustering and power law properties of the Graph.
-
random Intersection Graph process
Workshop on Algorithms and Models for the Web-Graph, 2013Co-Authors: Mindaugas Bloznelis, Michal KaronskiAbstract:We introduce a random Intersection Graph process aimed at modeling sparse evolving affiliation networks. We establish the asymptotic degree distribution and provide explicit asymptotic formulas for assortativity and clustering coefficients showing how these edge dependence characteristics vary over time.
-
degree distribution of an inhomogeneous random Intersection Graph
Electronic Journal of Combinatorics, 2013Co-Authors: Mindaugas Bloznelis, Julius DamarackasAbstract:We show the asymptotic degree distribution of the typical vertex of a sparse inhomogeneous random Intersection Graph.
-
random Intersection Graph process
arXiv: Probability, 2013Co-Authors: Mindaugas Bloznelis, Michal KaronskiAbstract:We introduce a random Intersection Graph process aimed at modeling sparse evolving affiliation networks that admit tunable (power law) degree distribution and assortativity and clustering coefficients. We show the asymptotic degree distribution and provide explicit asymptotic formulas for assortativity and clustering coefficients.
-
the largest component in an inhomogeneous random Intersection Graph with clustering
Electronic Journal of Combinatorics, 2010Co-Authors: Mindaugas BloznelisAbstract:Given integers $n$ and $m=\lfloor\beta n \rfloor$ and a probability measure $Q$ on $\{0, 1,\dots, m\}$, consider the random Intersection Graph on the vertex set $[n]=\{1,2,\dots, n\}$ where $i,j\in [n]$ are declared adjacent whenever $S(i)\cap S(j)\neq\emptyset$. Here $S(1),\dots, S(n)$ denote the iid random subsets of $[m]$ with the distribution $\bf{P}(S(i)=A)={{m}\choose{|A|}}^{-1}Q(|A|)$, $A\subset [m]$. For sparse random Intersection Graphs, we establish a first-order asymptotic as $n\to \infty$ for the order of the largest connected component $N_1=n(1-Q(0))\rho+o_P(n)$. Here $\rho$ is the average of nonextinction probabilities of a related multitype Poisson branching process.
Katarzyna Rybarczyk - One of the best experts on this subject based on the ideXlab platform.
-
Constructions of independent sets in random Intersection Graphs
Theoretical Computer Science, 2014Co-Authors: Katarzyna RybarczykAbstract:This paper concerns constructing independent sets in a random Intersection Graph. We concentrate on two cases of the model: a binomial and a uniform random Intersection Graph. For both models we analyse two greedy algorithms and prove that they find asymptotically almost optimal independent sets. We provide detailed analysis of the presented algorithms and give tight bounds on the independence number for the studied models. Moreover we determine the range of parameters for which greedy algorithms give better results for a random Intersection Graph than this is in the case of an Erd?s-Renyi random Graph G ( n , p ? ) .
-
The coupling method for inhomogeneous random Intersection Graphs
arXiv: Combinatorics, 2013Co-Authors: Katarzyna RybarczykAbstract:We present new results concerning threshold functions for a wide family of random Intersection Graphs. To this end we apply the coupling method used for establishing threshold functions for homogeneous random Intersection Graphs introduced by Karo\'nski, Scheinerman, and Singer--Cohen. In the case of inhomogeneous random Intersection Graphs the method has to be considerably modified and extended. By means of the altered method we are able to establish threshold functions for a general random Intersection Graph for such properties as $k$-connectivity, matching containment or hamiltonicity. Moreover using the new approach we manage to sharpen the best known results concerning homogeneous random Intersection Graph.
-
Sharp threshold functions via a coupling method
The Seventh European Conference on Combinatorics Graph Theory and Applications, 2013Co-Authors: Katarzyna RybarczykAbstract:We will present a new method used to establish threshold functions in the random Intersection Graph model. The method relies on a coupling of a random Intersection Graph with a random Graph similar to an Erdős and Renyi random Graph. Formerly a simple version of the technique was used in the case of homogeneous random Intersection Graphs. Now it is considerably modified and extended in order to be applied in the general case. By means of the method we are able to establish threshold functions for the general random Intersection Graph model for monotone properties. Moreover the new approach allows to sharpen considerably the best known results concerning threshold functions for homogeneous random Intersection Graph. We outline the main results obtained in [10].
-
diameter connectivity and phase transition of the uniform random Intersection Graph
Discrete Mathematics, 2011Co-Authors: Katarzyna RybarczykAbstract:We study properties of the uniform random Intersection Graph model G(n,m,d). We find asymptotic estimates on the diameter of the largest connected component of the Graph near the phase transition and connectivity thresholds. Moreover we manage to prove an asymptotically tight bound for the connectivity and phase transition thresholds for all possible ranges of d, which has not been obtained before. The main motivation of our research is the usage of the random Intersection Graph model in the studies of wireless sensor networks.
-
equivalence of a random Intersection Graph and g n p
Random Structures and Algorithms, 2011Co-Authors: Katarzyna RybarczykAbstract:We solve the conjecture of Fill, Scheinerman and Singer-Cohen (Random Struct Algorithms 16 (2000), 156–176) and show equivalence of sharp threshold functions of a random Intersection Graph ${\cal g}$ **image** (n,m,p) with m ≥ n3 and a Graph G(n,p) with independent edges. Moreover we prove sharper equivalence results under some additional assumptions. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2011 © 2011 Wiley Periodicals, Inc.
James R Lee - One of the best experts on this subject based on the ideXlab platform.
-
ITCS - Separators in Region Intersection Graphs
2017Co-Authors: James R LeeAbstract:For undirected Graphs G=(V,E) and G_0=(V_0,E_0), say that G is a region Intersection Graph over G_0 if there is a family of connected subsets {R_u \subseteq V_0 : u \in V} of G_0 such that {u,v} \in E \iff R_u \cap R_v \neq \emptyset. We show if G_0 excludes the complete Graph K_h as a minor for some h \geq 1, then every region Intersection Graph G over G_0 with m edges has a balanced separator with at most c_h \sqrt{m} nodes, where c_h is a constant depending only on h. If G additionally has uniformly bounded vertex degrees, then such a separator is found by spectral partitioning. A string Graph is the Intersection Graph of continuous arcs in the plane. String Graphs are precisely region Intersection Graphs over planar Graphs. Thus the preceding result implies that every string Graph with m edges has a balanced separator of size O(\sqrt{m}). This bound is optimal, as it generalizes the planar separator theorem. It confirms a conjecture of Fox and Pach (2010), and improves over the O(\sqrt{m} \log m) bound of Matousek (2013).
-
separators in region Intersection Graphs
Conference on Innovations in Theoretical Computer Science, 2017Co-Authors: James R LeeAbstract:For undirected Graphs G=(V,E) and G_0=(V_0,E_0), say that G is a region Intersection Graph over G_0 if there is a family of connected subsets {R_u \subseteq V_0 : u \in V} of G_0 such that {u,v} \in E \iff R_u \cap R_v \neq \emptyset. We show if G_0 excludes the complete Graph K_h as a minor for some h \geq 1, then every region Intersection Graph G over G_0 with m edges has a balanced separator with at most c_h \sqrt{m} nodes, where c_h is a constant depending only on h. If G additionally has uniformly bounded vertex degrees, then such a separator is found by spectral partitioning. A string Graph is the Intersection Graph of continuous arcs in the plane. String Graphs are precisely region Intersection Graphs over planar Graphs. Thus the preceding result implies that every string Graph with m edges has a balanced separator of size O(\sqrt{m}). This bound is optimal, as it generalizes the planar separator theorem. It confirms a conjecture of Fox and Pach (2010), and improves over the O(\sqrt{m} \log m) bound of Matousek (2013).
-
separators in region Intersection Graphs
arXiv: Combinatorics, 2016Co-Authors: James R LeeAbstract:For undirected Graphs $G=(V,E)$ and $G_0=(V_0,E_0)$, say that $G$ is a region Intersection Graph over $G_0$ if there is a family of connected subsets $\{ R_u \subseteq V_0 : u \in V \}$ of $G_0$ such that $\{u,v\} \in E \iff R_u \cap R_v \neq \emptyset$. We show if $G_0$ excludes the complete Graph $K_h$ as a minor for some $h \geq 1$, then every region Intersection Graph $G$ over $G_0$ with $m$ edges has a balanced separator with at most $c_h \sqrt{m}$ nodes, where $c_h$ is a constant depending only on $h$. If $G$ additionally has uniformly bounded vertex degrees, then such a separator is found by spectral partitioning. A string Graph is the Intersection Graph of continuous arcs in the plane. The preceding result implies that every string Graph with $m$ edges has a balanced separator of size $O(\sqrt{m})$. This bound is optimal, as it generalizes the planar separator theorem. It confirms a conjecture of Fox and Pach (2010), and improves over the $O(\sqrt{m} \log m)$ bound of Matousek (2013).
J. M. A. Tanchoco - One of the best experts on this subject based on the ideXlab platform.
-
Intersection Graph method for AGV flow path design
International Journal of Production Research, 1991Co-Authors: David Sinriech, J. M. A. TanchocoAbstract:In this paper, we introduce the Intersection Graph Method for solving the AGV Flow Path Optimization Model developed by Kaspi and Tanchoco (1990). A branch-and-bound procedure is described wherein only a reduced subset of all nodes in the flow path network is considered. Only Intersection nodes are used to obtain optimal solutions. Two examples are given to illustrate the proposed method.
Daniel Gonçalves - One of the best experts on this subject based on the ideXlab platform.
-
Homothetic triangle representations of planar Graphs
Journal of Graph Algorithms and Applications, 2019Co-Authors: Daniel Gonçalves, Benjamin Lévêque, Alexandre PinlouAbstract:We prove that every planar Graph is the Intersection Graph of homothetic triangles in the plane.
-
Dushnik-Miller dimension of contact systems of d -dimensional boxes
Electronic Notes in Discrete Mathematics, 2017Co-Authors: Mathew Francis, Daniel GonçalvesAbstract:Planar Graphs are the Graphs with Dushnik-Miller dimension at most three (W. Schnyder, Planar Graphs and poset dimension, Order 5, 323-343, 1989). Consider the Intersection Graph of interior disjoint axis-parallel rectangles in the plane. It is known that if at most three rectangles intersect on a point, then this Intersection Graph is planar, that is it has Dushnik-Miller dimension at most three. This paper aims at generalizing this from the plane to by considering tilings of with axis parallel boxes, where at most boxes intersect on a point. Such tilings induce simplicial complexes and we will show that those simplicial complexes have Dushnik-Miller dimension at most.
-
Planar Graphs Have 1-string Representations
Discrete and Computational Geometry, 2010Co-Authors: Jeremie Chalopin, Daniel Gonçalves, Pascal OchemAbstract:We prove that every planar Graph is an Intersection Graph of strings in the plane such that any two strings intersect at most once.
-
every planar Graph is the Intersection Graph of segments in the plane extended abstract
Symposium on the Theory of Computing, 2009Co-Authors: Jeremie Chalopin, Daniel GonçalvesAbstract:Given a set S of segments in the plane, the Intersection Graph of S is the Graph with vertex set S in which two vertices are adjacent if and only if the corresponding two segments intersect. We prove a conjecture of Scheinerman (PhD Thesis, Princeton University, 1984) that every planar Graph is the Intersection Graph of some segments in the plane.
