Abstract: We give an efficient local search
algorithm that computes a good vertex coloring of a graph $G$. In
order to better illustrate this local search method, we view local
moves as selfish moves in a suitably defined game. In particular,
given a graph $G=(V,E)$ of $n$ vertices and $m$ edges, we define
the \emph{graph coloring game} $\Gamma(G)$ as a strategic game
where the set of players is the set of vertices and the players
share the same action set, which is a set of $n$ colors. The
payoff that a vertex $v$ receives, given the actions chosen by all
vertices, equals the total number of vertices that have chosen the
same color as $v$, unless a neighbor of $v$ has also chosen the
same color, in which case the payoff of $v$ is 0. We show:
\begin{itemize}
\item The game $\Gamma(G)$ has always pure Nash equilibria. Each
pure equilibrium is a proper coloring of $G$. Furthermore, there
exists a pure equilibrium that corresponds to an optimum coloring.
\item We give a polynomial time algorithm $\mathcal{A}$ which
computes a pure Nash equilibrium of $\Gamma(G)$. \item The total
number, $k$, of colors used in \emph{any} pure Nash equilibrium
(and thus achieved by $\mathcal{A}$) is $k\leq\min\{\Delta_2+1,
\frac{n+\omega}{2}, \frac{1+\sqrt{1+8m}}{2}, n-\alpha+1\}$, where
$\omega, \alpha$ are the clique number and the independence number
of $G$ and $\Delta_2$ is the maximum degree that a vertex can have
subject to the condition that it is adjacent to at least one
vertex of equal or greater degree. ($\Delta_2$ is no more than the
maximum degree $\Delta$ of $G$.) \item Thus, in fact, we propose
here a \emph{new}, \emph{efficient} coloring method that achieves
a number of colors \emph{satisfying (together) the known general
upper bounds on the chromatic number $\chi$}. Our method is also
an alternative general way of \emph{proving},
\emph{constructively}, all these bounds. \item Finally, we show
how to strengthen our method (staying in polynomial time) so that
it avoids ``bad'' pure Nash equilibria (i.e. those admitting a
number of colors $k$ far away from $\chi$). In particular, we show
that our enhanced method colors \emph{optimally} dense random
$q$-partite graphs (of fixed $q$) with high probability.
\end{itemize}
Abstract: We investigate the problem of efficient data collection in wireless sensor networks where both the sensors and the sink move. We especially study the important, realistic case where the spatial distribution of sensors is non-uniform and their mobility is diverse and dynamic. The basic idea of our protocol is for the sink to benefit of the local information that sensors spread in the network as they move, in order
to extract current local conditions and accordingly adjust its trajectory. Thus, sensory motion anyway present in the network serves as a low cost replacement of network information propagation. In particular, we investigate two variations of our method: a)the greedy motion of the sink towards the region of highest density each time and b)taking into account the aggregate density in wider network regions. An extensive comparative evaluation to relevant data collection methods (both randomized and optimized deterministic), demonstrates that our approach achieves significant performance gains, especially in non-uniform placements (but also in uniform ones). In fact, the greedy version of our approach is more suitable in networks where the concentration regions appear in a spatially balanced manner, while the aggregate scheme is more appropriate in networks where the concentration areas are geographically correlated.
Abstract: We investigate the problem of efficient data collection in wireless sensor networks where both the sensors and the sink move. We especially study the important, realistic case where the spatial distribution of sensors is non-uniform and their mobility is diverse and dynamic. The basic idea of our protocol is for the sink to benefit of the local information that sensors spread in the network as they move, in order to extract current local conditions and accordingly adjust its trajectory. Thus, sensory motion anyway present in the network serves as a low cost replacement of network information propagation. In particular, we investigate two variations of our method: a) the greedy motion of the sink towards the region of highest density each time and b) taking into account the aggregate density in wider network regions. An extensive comparative evaluation to relevant data collection methods (both randomized and optimized deterministic), demonstrates that our approach achieves significant performance gains, especially in non-uniform placements (but also in uniform ones). In fact, the greedy version of our approach is more suitable in networks where the concentration regions appear in a spatially balanced manner, while the aggregate scheme is more appropriate in networks where the concentration areas are geographically correlated. We also investigate the case of multiple sinks by suggesting appropriate distributed coordination methods.
Abstract: For many random Constraint Satisfaction Problems, by now, we have asymptotically tight estimates of
the largest constraint density for which they have solutions. At the same time, all known polynomial-time algorithms
for many of these problems already completely fail to find solutions at much smaller densities. For example, it is
well-known that it is easy to color a randomgraph using twice as many colors as its chromatic number. Indeed, some
of the simplest possible coloring algorithms already achieve this goal. Given the simplicity of those algorithms, one
would expect there is a lot of room for improvement. Yet, to date, no algorithm is known that uses (2 - o)÷ colors,
in spite of efforts by numerous researchers over the years.
In view of the remarkable resilience of this factor of 2 against every algorithm hurled at it, we believe it is natural to
inquire into its origin. We do so by analyzing the evolution of the set of k-colorings of a randomgraph, viewed as a
subset of {1, . . . , k}n, as edges are added. We prove that the factor of 2 corresponds in a precise mathematical sense
to a phase transition in the geometry of this set. Roughly, the set of k-colorings looks like a giant ball for k ? 2÷, but
like an error-correcting code for k ? (2 - o)÷. We prove that a completely analogous phase transition also occurs both in random k-SAT and in random hypergraph 2-coloring. And that for each problem, its location corresponds precisely with the point were all known polynomial-time algorithms fail. To prove our results we develop a general technique that allows us to prove rigorously much of the celebrated 1-step Replica-Symmetry-Breaking hypothesis
of statistical physics for random CSPs.
Abstract: For a number of optimization problems on randomgraphs
and hypergraphs, e.g., k-colorings, there is a very big gap between the
largest average degree for which known polynomial-time algorithms can
find solutions, and the largest average degree for which solutions provably
exist. We study this phenomenon by examining how sets of solutions
evolve as edges are added.We prove in a precise mathematical sense that,
for each problem studied, the barrier faced by algorithms corresponds
to a phase transition in the problems solution-space geometry. Roughly
speaking, at some problem-specific critical density, the set of solutions
shatters and goes from being a single giant ball to exponentially many,
well-separated, tiny pieces. All known polynomial-time algorithms work
in the ball regime, but stop as soon as the shattering occurs. Besides
giving a geometric view of the solution space of random instances our
results provide novel constructions of one-way functions.
Abstract: In this work we study the important problem of colouring squares of planar graphs (SQPG). We design and implement two new algorithms that colour in a different way SQPG. We call these algorithms MDsatur and RC. We have also implemented and experimentally evaluated the performance of most of the known approximation colouring algorithms for SQPG [14, 6, 4, 10]. We compare the quality of the colourings achieved by these algorithms, with the colourings obtained by our algorithms and with the results obtained from two well-known greedy colouring heuristics. The heuristics are mainly used for comparison reasons and unexpectedly give very good results. Our algorithm MDsatur outperforms the known algorithms as shown by the extensive experiments we have carried out.
The planar graph instances whose squares are used in our experiments are “non-extremal” graphs obtained by LEDA and hard colourable graph instances that we construct.
The most interesting conclusions of our experimental study are:
1) all colouring algorithms considered here have almost optimal performance on the squares of “non-extremal” planar graphs. 2) all known colouring algorithms especially designed for colouring SQPG, give significantly better results, even on hard to colour graphs, when the vertices of the input graph are randomly named. On the other hand, the performance of our algorithm, MDsatur, becomes worse in this case, however it still has the best performance compared to the others. MDsatur colours the tested graphs with 1.1 OPT colours in most of the cases, even on hard instances, where OPT denotes the number of colours in an optimal colouring. 3) we construct worst case instances for the algorithm of Fotakis el al. [6], which show that its theoretical analysis is tight.
Abstract: We investigate the problem of communication in an ad-hoc mobile network, that is, we assume the extreme case of a total absense of any fixed network infrastructure (for example a case of rapid deployment of a set of mobile hosts in an unknown terrain). We propose, in such a case, that a small subset of the deployed hosts (which we call the support) should be used for network operations. However, the vast majority of the hosts are moving arbitrarily according to application needs.
We then provide a simple, correct and efficient protocol for communication that avoids message flooding. Our protocol manages to establish communication between any pair of mobile hosts in small, a-priori guaranteed expected time bounds even in the worst case of arbitrary motions of the hosts that not in the support (provided that they do not deliberately try to avoid the support). These time bounds, interestingly, do not depend, on the number of mobile hosts that do not belong in the support. They depend only on the size of the area of motions. Our protocol can be implemented in very efficient ways by exploiting knowledge of the space of motions or by adding more power to the hosts of the support.
Our results exploit and further develop some fundamental properties of random walks in finite graphs.
Abstract: We introduce a new model of
ad-hoc mobile networks, which we call hierarchical,
that are comprised of dense subnetworks of mobile
users (corresponding to highly populated
geographical areas, such as cities),
interconnected across access ports
by sparse but frequently used connections
(such as highways).
For such networks, we present
an efficient routing protocol which extends
the idea (introduced in WAE00) of exploiting the co-ordinated
motion of a small part of an ad-hoc mobile
network (the ``support'') to achieve
very fast communication between any two mobile users of the network.
The basic idea of the new protocol presented here is, instead
of using a unique (large) support for the whole network,
to employ a hierarchy of (small) supports (one for each city)
and also take advantage of the regular traffic
of mobile users across the interconnection highways to communicate
between cities.
We combine here theoretical analysis (average case estimations based on random walk properties) and experimental implementations (carried out using the LEDA platform) to claim and validate results showing that such a hierarchical routing approach is,
for this class of ad-hoc mobile networks, significantly more efficient than a simple extension of the
basic ``support'' idea presented in WAE00.
Abstract: We have conducted an extensive experimental study on algorithms for fully dynamic transitive
closure. We have implemented the recent fully dynamic algorithms by King [1999], Roditty [2003],
Roditty and Zwick [2002, 2004], and Demetrescu and Italiano [2000, 2005] along with several variants
and compared them to pseudo fully dynamic and simple-minded algorithms developed in a
previous study [Frigioni et al. 2001].We tested and compared these implementations on random inputs,
synthetic (worst-case) inputs, and on inputs motivated by real-world graphs. Our experiments
reveal that some of the dynamic algorithms can really be of practical value in many situations.
Abstract: We have conducted an extensive experimental study on algorithms for fully dynamic transitive
closure. We have implemented the recent fully dynamic algorithms by King [1999], Roditty [2003],
Roditty and Zwick [2002, 2004], and Demetrescu and Italiano [2000, 2005] along with several variants
and compared them to pseudo fully dynamic and simple-minded algorithms developed in a
previous study [Frigioni et al. 2001].We tested and compared these implementations on random inputs,
synthetic (worst-case) inputs, and on inputs motivated by real-world graphs. Our experiments
reveal that some of the dynamic algorithms can really be of practical value in many situations.
Abstract: We perform an extensive experimental study of several dynamic algorithms for transitive closure. In particular, we implemented algorithms given by Italiano, Yellin, Cicerone et al., and two recent randomized algorithms by Henzinger and King. We propose a fine-tuned version of Italiano's algorithms as well as a new variant of them, both of which were always faster than any of the other implementations of the dynamic algorithms. We also considered simple-minded algorithms that were easy to implement and likely to be fast in practice. Wetested and compared the above implementations on random inputs, on non-random inputs that are worst-case inputs for the dynamic algorithms, and on an input motivated by a real-world graph.
Abstract: An ad-hoc mobile network is a collection of mobile hosts, with wireless communication capability, forming a temporary network without the aid of any established fixed infrastructure. In such a (dynamically changing) network it is not at all easy to avoid broadcasting (and flooding).
In this paper we propose, theoretically analyse and experimentally validate a new and efficient protocol for pairwise communication. The protocol exploits the co-ordinated motion of a small part of the network (i.e. it is a semi-compulsory protocol) in order to provide to various senders and receivers an efficient support for message passing. Our implementation platform is the LEDA system and we have tested the protocol for three classes of graphs (grids, randomgraphs and bipartite multi-stage graphs) each ing a different ?motion topology?.
Our theoretical analysis (based on properties of random walks) and our experimental measurements indicate that only a small fraction of the mobile stations are enough to be exploited by the support in order to achieve very fast communication between any pair of mobile stations.
Abstract: We introduce a new model of ad-hoc mobile networks,
which we call hierarchical, that are comprised of
dense subnetworks of mobile users (corresponding to highly
populated geographical areas), interconnected across access
ports by sparse but frequently used connections.
To implement communication in such a case, a possible
solution would be to install a very fast (yet limited) backbone
interconnecting such highly populated mobile user areas, while
employing a hierarchy of (small) supports (one for each lower level
site). This fast backbone provides a limited number of access
ports within these dense areas of mobile users.
We combine here theoretical analysis (average case estimations based on
random walk properties) to claim and validate
results showing that such a hierarchical routing approach is,
for this class of ad-hoc mobile networks, significantly
more efficient than a simple extension of the
basic ``support'' idea presented in [WAE00,DISC01].
Abstract: Consider k particles, 1 red and k–1 white, chasing each other on the nodes of a graph G. If the red one catches one of the white, it ldquoinfectsrdquo it with its color. The newly red particles are now available to infect more white ones. When is it the case that all white will become red? It turns out that this simple question is an instance of information propagation between random walks and has important applications to mobile computing where a set of mobile hosts acts as an intermediary for the spread of information.
In this paper we model this problem by k concurrent random walks, one corresponding to the red particle and k–1 to the white ones. The infection time Tk of infecting all the white particles with red color is then a random variable that depends on k, the initial position of the particles, the number of nodes and edges of the graph, as well as on the structure of the graph.
We easily get that an upper bound on the expected value of Tk is the worst case (over all initial positions) expected meeting time m* of two random walks multiplied by THgr (log k). We demonstrate that this is, indeed, a tight bound; i.e. there is a graph G (a special case of the ldquolollipoprdquo graph), a range of values kgraphs are tight.
Abstract: We study the following Constrained Bipartite Edge Coloring problem: We are given a bipartite graph G=(U,V,E) of maximum degree I with n vertices, in which some of the edges have been legally colored with c colors. We wish to complete the coloring of the edges of G minimizing the total number of colors used. The problem has been proved to be NP-hard even for bipartite graphs of maximum degree three. Two special cases of the problem have been previously considered and tight upper and ower bounds on the optimal number of colors were proved. The upper bounds led to 3/2-approximation algorithms for both problems. In this paper we present a randomized (1.37+o(1))-approximation algorithm for the general problem in the case where max{l,c} = {\`u}(ln n). Our techniques are motivated by recent works on the Circular Arc Coloring problem and are essentially different and simpler than the existing ones.
Abstract: Motivated by the wavelength assignment problem in WDM optical networks, we study path coloring problems in graphs. Given a set of paths P on a graph G, the path coloring problem is to color the paths of P so that no two paths traversing the same edge of G are assigned the same color and the total number of colors used is minimized. The problem has been proved to be NP-hard even for trees and rings.
Using optimal solutions to fractional path coloring, a natural relaxation of path coloring, on which we apply a randomized rounding technique combined with existing coloring algorithms, we obtain new upper bounds on the minimum number of colors sufficient to color any set of paths on any graph. The upper bounds are either existential or constructive.
The existential upper bounds significantly improve existing ones provided that the cost of the optimal fractional path coloring is sufficiently large and the dilation of the set of paths is small. Our algorithmic results include improved approximation algorithms for path coloring in rings and in bidirected trees. Our results extend to variations of the original path coloring problem arizing in multifiber WDM optical networks.
Abstract: We give a deterministic polynomial-time algorithm which for any given average degree d and asymptotically almost all randomgraphs G in G(n, m = [d/2 n]) outputs a cut of G whose ratio (in cardinality) with the maximum cut is at least 0.952. We remind the reader that it is known that unless P=NP, for no constant {\aa}>0 is there a Max-Cut approximation algorithm that for all inputs achieves an approximation ratio of (16/17) +{\aa} (16/17 < 0.94118).
Abstract: We consider the Moran process, as generalized by Lieberman, Hauert and Nowak (Nature, 433:312--316, 2005). A population resides on the vertices of a finite, connected, undirected graph and, at each time step, an individual is chosen at random with probability proportional to its assigned 'fitness' value. It reproduces, placing a copy of itself on a neighbouring vertex chosen uniformly at random, replacing the individual that was there. The initial population consists of a single mutant of fitness r>0 placed uniformly at random, with every other vertex occupied by an individual of fitness 1. The main quantities of interest are the probabilities that the descendants of the initial mutant come to occupy the whole graph (fixation) and that they die out (extinction); almost surely, these are the only possibilities. In general, exact computation of these quantities by standard Markov chain techniques requires solving a system of linear equations of size exponential in the order of the graph so is not feasible. We show that, with high probability, the number of steps needed to reach fixation or extinction is bounded by a polynomial in the number of vertices in the graph. This bound allows us to construct fully polynomial randomized approximation schemes (FPRAS) for the probability of fixation (when r≥1) and of extinction (for all r>0).
Abstract: An intersection graph of n vertices assumes that each vertex is equipped with a subset of a global label set. Two vertices share an edge
when their label sets intersect. Random Intersection Graphs (RIGs) (as defined in [18, 31]) consider label sets formed by the following experiment:
each vertex, independently and uniformly, examines all the labels (m in total) one by one. Each examination is independent and the vertex
succeeds to put the label in her set with probability p. Such graphs nicely capture interactions in networks due to sharing of resources among nodes.
We study here the problem of efficiently coloring (and of finding upper bounds to the chromatic number) of RIGs. We concentrate in a range
of parameters not examined in the literature, namely: (a) m = n{\'a} for less than 1 (in this range, RIGs differ substantially from the Erd¨os- Renyi randomgraphs) and (b) the selection probability p is quite high
(e.g. at least ln2 n m in our algorithm) and disallows direct greedy colouring methods.
We manage to get the following results:
For the case mp ln n, for any constant < 1 − , we prove that np colours are enough to colour most of the vertices of the graph with high probability (whp). This means that even for quite dense
graphs, using the same number of colours as those needed to properly colour the clique induced by any label suffices to colour almost all of the vertices of the graph. Note also that this range of values of m, p
is quite wider than the one studied in [4].
� We propose and analyze an algorithm CliqueColour for finding a proper colouring of a random instance of Gn,m,p, for any mp >=ln2 n. The algorithm uses information of the label sets assigned to the
vertices of Gn,m,p and runs in O (n2mp2/ln n) time, which is polynomial in n and m. We also show by a reduction to the uniform random
intersection graphs model that the number of colours required by the algorithm are of the correct order of magnitude with the actual
chromatic number of Gn,m,p.
⋆ This work was partially supported by the ICT Programme of the European Union under contract number ICT-2008-215270 (FRONTS). Also supported by Research Training Group GK-693 of the Paderborn Institute for Scientific Computation
(PaSCo).
� We finally compare the problem of finding a proper colouring for Gn,m,p to that of colouring hypergraphs so that no edge is monochromatic.We show how one can find in polynomial time a k-colouring of the vertices of Gn,m,p, for any integer k, such that no clique induced by only one label in Gn,m,p is monochromatic. Our techniques are novel and try to exploit as much as possible the hidden structure of random intersection graphs in this interesting range.
Abstract: We investigate random intersection graphs, a combinatorial model that quite accurately abstracts distributed networks with local interactions between nodes blindly sharing critical resources from a limited globally available domain. We study important combinatorial properties (independence and hamiltonicity) of such graphs. These properties relate crucially to algorithmic design for important problems (like secure communication and frequency assignment) in distributed networks characterized by dense, local interactions and resource limitations, such as sensor networks. In particular, we prove that, interestingly, a small constant number of random, resource selections suffices to make the graph hamiltonian and we provide tight evaluations of the independence number of these graphs.
Abstract: In this work, we overview some results concerning communication combinatorial properties in random intersection graphs and uniform random intersection graphs. These properties relate crucially to algorithmic design for important problems (like secure communication and frequency assignment) in distributed networks characterized by dense, local interactions and resource limitations, such as sensor networks. In particular, we present and discuss results concerning the existence of large independent sets of vertices whp in random instances of each of these models. As the main contribution of our paper, we introduce a new, general model, which we denote G(V, χ, f). In this model, V is a set of vertices and χ is a set of m vectors in ℝm. Furthermore, f is a probability distribution over the powerset 2χ of subsets of χ. Every vertex selects a random subset of vectors according to the probability f and two vertices are connected according to a general intersection rule depending on their assigned set of vectors. Apparently, this new general model seems to be able to simulate other known randomgraph models, by carefully describing its intersection rule.
Abstract: We address an important communication issue arising in
wireless cellular networks that utilize frequency division
multiplexing (FDM) technology. In such networks, many
users within the same geographical region (cell) can communicate
simultaneously with other users of the network
using distinct frequencies. The spectrum of the available
frequencies is limited; thus, efficient solutions to the call
controlproblemareessential.Theobjectiveofthecallcontrol
problem is, given a spectrum of available frequencies
and users that wish tocommunicate, to maximize the benefit,
i.e., the number of users that communicate without
signalinterference.Weconsidercellularnetworksofreuse
distance k ≥ 2 and we study the online version of the
problem using competitive analysis. In cellular networks
of reuse distance 2, the previously best known algorithm
that beats the lower bound of 3 on the competitiveness
of deterministic algorithms, works on networks with one
frequency, achieves a competitive ratio against oblivious
adversaries, which is between 2.469 and 2.651, and uses
a number of random bits at least proportional to the size
of the network.We significantly improve this result by presentingaseriesofsimplerandomizedalgorithmsthathave
competitiveratiossignificantlysmallerthan3,workonnetworks
with arbitrarily many frequencies, and use only a
constant number of random bits or a comparable weak
random source. The best competitiveness upper bound
we obtain is 16/7 using only four random bits. In cellular
networks of reuse distance k > 2, we present simple
randomized online call control algorithms with competitive
ratios, which significantly beat the lower bounds on
the competitiveness of deterministic ones and use only
O(log k )randombits. Also,weshownewlowerboundson
thecompetitivenessofonlinecallcontrolalgorithmsincellularnetworksofanyreusedistance.
Inparticular,weshow
thatnoonline algorithm can achieve competitive ratio better
than 2, 25/12, and 2.5, in cellular networks with reuse
distancek ∈ {2, 3, 4},k = 5,andk ≥ 6, respectively.
Abstract: In this work we investigate the problem of communication among mobile hosts, one of the most fundamental problems in ad-hoc mobile networks that is at the core of many algorithms. Our work investigates the extreme case of total absence of any fixed network backbone or centralized administration, instantly forming networks based only on mobile hosts with wireless communication capabilities, where topological connectivity is subject to frequent, unpredictable change.
For such dynamically changing networks we propose a set of protocols which exploit the coordinated (by the protocol) motion of a small part of the network in order to manage network operations. We show that such protocols can be designed to work correctly and efficiently for communication by avoiding message flooding. Our protocols manage to establish communication between any pair of mobile hosts in small, a-priori guaranteed expected time bounds. Our results exploit and further develop some fundamental properties of random walks in finite graph.
Apart from studying the general case, we identify two practical and interesting cases of ad-hoc mobile networks: a) hierarchical ad-hoc networks, b) highly changing ad-hoc networks, for which we propose protocols that efficiently deal with the problem of basic communication.
We have conducted a set of extensive experiments, comprised of thousands of mobile hosts in order to validate the theoretical results and show that our protocols achieve very efficient communication under different scenaria.
Abstract: Wireless Sensor Networks consist of a large number of small, autonomous devices, that are able to interact with their inveronment by sensing and collaborate to fulfill their tasks, as, usually, a single node is incapable of doing so; and they use wireless communication to enable this collaboration. Each device has limited computational and energy resources, thus a basic issue in the applicastions of wireless sensor networks is the low energy consumption and hence, the maximization of the network lifetime.
The collected data is disseminated to a static control point – data sink in the network, using node to node - multi-hop data propagation. However, sensor devices consume significant amounts of energy in addition to increased implementation complexity, since a routing protocol is executed. Also, a point of failure emerges in the area near the control center where nodes relay the data from nodes that are farther away. Recently, a new approach has been developed that shifts the burden from the sensor nodes to the sink. The main idea is that the sink has significant and easily replenishable energy reserves and can move inside the area the sensor network is deployed, in order to acquire the data collected by the sensor nodes at very low energy cost. However, the need to visit all the regions of the network may result in large delivery delays.
In this work we have developed protocols that control the movement of the sink in wireless sensor networks with non-uniform deployment of the sensor nodes, in order to succeed an efficient (with respect to both energy and latency) data collection. More specifically, a graph formation phase is executed by the sink during the initialization: the network area is partitioned in equal square regions, where the sink, pauses for a certain amount of time, during the network traversal, in order to collect data.
We propose two network traversal methods, a deterministic and a random one. When the sink moves in a random manner, the selection of the next area to visit is done in a biased random manner depending on the frequency of visits of its neighbor areas. Thus, less frequently visited areas are favored. Moreover, our method locally determines the stop time needed to serve each region with respect to some global network resources, such as the initial energy reserves of the nodes and the density of the region, stopping for a greater time interval at regions with higher density, and hence more traffic load. In this way, we achieve accelerated coverage of the network as well as fairness in the service time of each region.Besides randomized mobility, we also propose an optimized deterministic trajectory without visit overlaps, including direct (one-hop) sensor-to-sink data transmissions only.
We evaluate our methods via simulation, in diverse network settings and comparatively to related state of the art solutions. Our findings demonstrate significant latency and energy consumption improvements, compared to previous research.
Abstract: We study here the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types. The vertices may have a few additional possible states and can interact in pairs only if they share an edge. Any (population) protocol is required to stabilize in the initial majority. We first present and analyze a protocol with 4 states per vertex that always computes the initial majority value, under any fair scheduler. As we prove, this protocol is optimal, in the sense that there is no population protocol that always computes majority with fewer than 4 states per vertex. However this does not rule out the existence of a protocol with 3 states per vertex that is correct with high probability. To this end, we examine a very natural majority protocol with 3 states per vertex, introduced in [Angluin et al. 2008] where its performance has been analyzed for the clique graph. We study the performance of this protocol in arbitrary networks. We prove that, when the two initial states are put uniformly at random on the vertices, this protocol converges to the initial majority with probability higher than the probability of converging to the initial minority. In contrast, we present an infinite family of graphs, on which the protocol can fail whp, even when the difference between the initial majority and the initial minority is n−Θ(lnn). We also present another infinite family of graphs in which the protocol of Angluin et al. takes an expected exponential time to converge. These two negative results build upon a very positive result concerning the robustness of the protocol on the clique. Surprisingly, the resistance of the clique to failure causes the failure in general graphs. Our techniques use new domination and coupling arguments for suitably defined processes whose dynamics capture the antagonism between the states involved.
Abstract: In this paper we consider communication issues arising in mobile networks that utilize Frequency Division Multiplexing (FDM) technology. In such networks, many users within the same geographical region can communicate simultaneously with other users of the network using distinct frequencies. The spectrum of available frequencies is limited; thus, efficient solutions to the frequency allocation and the call control problem are essential. In the frequency allocation problem, given users that wish to communicate, the objective is to minimize the required spectrum of frequencies so that communication can be established without signal interference. The objective of the call control problem is, given a spectrum of available frequencies and users that wish to communicate, to maximize the number of users served. We consider cellular, planar, and arbitrary network topologies. In particular, we study the on-line version of both problems using competitive analysis. For frequency allocation in cellular networks, we improve the best known competitive ratio upper bound of 3 achieved by the folklore Fixed Allocation algorithm, by presenting an almost tight competitive analysis for the greedy algorithm; we prove that its competitive ratio is between 2.429 and 2.5. For the call control problem, we present the first randomized algorithm that beats the deterministic lower bound of 3 achieving a competitive ratio of 2.934 in cellular networks. Our analysis has interesting extensions to arbitrary networks. Also, using Yao's Minimax Principle, we prove two lower bounds of 1.857 and 2.086 on the competitive ratio of randomized call control algorithms for cellular and arbitrary planar networks, respectively.
Abstract: In this paper we consider communication issues arising in cellular (mobile) networks that utilize frequency division multiplexing (FDM) technology. In such networks, many users within the same geographical region can communicate simultaneously with other users of the network using distinct frequencies. The spectrum of available frequencies is limited; thus, efficient solutions to the frequency-allocation and the call-control problems are essential. In the frequency-allocation problem, given users that wish to communicate, the objective is to minimize the required spectrum of frequencies so that communication can be established without signal interference. The objective of the call-control problem is, given a spectrum of available frequencies and users that wish to communicate, to maximize the number of users served. We consider cellular, planar, and arbitrary network topologies.
In particular, we study the on-line version of both problems using competitive analysis. For frequency allocation in cellular networks, we improve the best known competitive ratio upper bound of 3 achieved by the folklore Fixed Allocation algorithm, by presenting an almost tight competitive analysis for the greedy algorithm; we prove that its competitive ratio is between 2.429 and 2.5 . For the call-control problem, we present the first randomized algorithm that beats the deterministic lower bound of 3 achieving a competitive ratio between 2.469 and 2.651 for cellular networks. Our analysis has interesting extensions to arbitrary networks. Also, using Yao's Minimax Principle, we prove two lower bounds of 1.857 and 2.086 on the competitive ratio of randomized call-control algorithms for cellular and arbitrary planar networks, respectively.
Abstract: We investigate important combinatorial and algorithmic properties of $G_{n, m, p}$ random intersection graphs. In particular, we prove that with high probability (a) random intersection graphs are expanders, (b) random walks on such graphs are ``rapidly mixing" (in particular they mix in logarithmic time) and (c) the cover time of random walks on such graphs is optimal (i.e. it is $\Theta(n \log{n})$). All results are proved for $p$ very close to the connectivity threshold and for the interesting, non-trivial range where random intersection graphs differ from classical $G_{n, p}$ randomgraphs.
Abstract: In this work we experimentally study the min order Radiocoloring problem (RCP) on Chordal, Split and Permutation graphs, which are three basic families of perfect graphs. This problem asks to find an assignment using the minimum number of colors to the vertices of a given graph G, so that each pair of vertices which are at distance at most two apart in G have different colors. RCP is an NP-Complete problem on chordal and split graphs [4]. For each of the three families, there are upper bounds or/and approximation algorithms known for minimum number of colors needed to radiocolor such a graph [4,10].
We design and implement radiocoloring heuristics for graphs of above families, which are based on the greedy heuristic. Also, for each one of the above families, we investigate whether there exists graph instances requiring a number of colors in order to be radiocolored, close to the best known upper bound for the family. Towards this goal, we present a number generators that produce graphs of the above families that require either (i) a large number of colors (compared to the best upper bound), in order to be radiocolored, called ldquoextremalrdquo graphs or (ii) a small number of colors, called ldquonon-extremalrdquoinstances. The experimental evaluation showed that random generated graph instances are in the most of the cases ldquonon-extremalrdquo graphs. Also, that greedy like heuristics performs very well in the most of the cases, especially for ldquonon-extremalrdquo graphs.
Abstract: We investigate the existence and efficient algorithmic
construction of close to optimal independent sets in random models
of intersection graphs. In particular, (a) we propose \emph{a new model} for random intersection graphs
($G_{n, m, \vec{p}}$) which includes the model of
\cite{RIG} (the ``uniform" random intersection graphs model) as an
important special case. We also define an interesting variation of
the model of random intersection graphs, similar in spirit to
random regular graphs. (b) For this model we derive \emph{exact formulae} for the mean
and variance of the number of independent sets of size $k$ (for
any $k$) in the graph. (c) We then propose and analyse \emph{three algorithms} for the
efficient construction of large independent sets in this model.
The first two are variations of the greedy technique while the
third is a totally new algorithm. Our algorithms are analysed for
the special case of uniform random intersection graphs.
Our analyses show that these algorithms succeed in finding
\emph{close to optimal} independent sets for an interesting range
of graph parameters.
Abstract: We extend here the Population Protocol model of Angluin et al. [2004] in order to model more powerful networks of very small resource-limited artefacts (agents) that are possibly mobile. Communication can happen only between pairs of artefacts. A communication graph (or digraph) denotes the permissible pairwise interactions. The main feature of our extended model is to allow edges of the communication graph, G, to have states that belong to a constant size set. We also allow edges to have readable only costs, whose values also belong to a constant size set. We then allow the protocol rules for pairwise interactions to modify the corresponding edge state. Thus, our protocol specifications are still independent of the population size and do not use agent ids, i.e. they preserve scalability, uniformity and anonymity. Our Mediated Population Protocols (MPP) can stably compute graph properties of the communication graph. We show this for the properties of maximal matchings (in undirected communication graphs), also for finding the transitive closure of directed graphs and for finding all edges of small cost. We demonstrate that our mediated protocols are stronger than the classical population protocols, by presenting a mediated protocol that stably computes the product of two positive integers, when G is the complete graph. This is not a semilinear predicate. To show this fact, we state and prove a general Theorem about the Composition of two stably computing mediated population protocols. We also show that all predicates stably computable in our model are (non-uniformly) in the class NSPACE(m), where m is the number of edges of the communication graph. We also define Randomized MPP and show that, any Peano predicate accepted by a MPP, can be verified in deterministic Polynomial Time.
Abstract: In this work we consider temporal graphs, i.e. graphs, each edge of which isassigned a set of discrete time-labels drawn from a set of integers. The labelsof an edge indicate the discrete moments in time at which the edge isavailable. We also consider temporal paths in a temporal graph, i.e. pathswhose edges are assigned a strictly increasing sequence of labels. Furthermore,we assume the uniform case (UNI-CASE), in which every edge of a graph isassigned exactly one time label from a set of integers and the time labelsassigned to the edges of the graph are chosen randomly and independently, withthe selection following the uniform distribution. We call uniform randomtemporal graphs the graphs that satisfy the UNI-CASE. We begin by deriving theexpected number of temporal paths of a given length in the uniform randomtemporal clique. We define the term temporal distance of two vertices, which isthe arrival time, i.e. the time-label of the last edge, of the temporal paththat connects those vertices, which has the smallest arrival time amongst alltemporal paths that connect those vertices. We then propose and study twostatistical properties of temporal graphs. One is the maximum expected temporaldistance which is, as the term indicates, the maximum of all expected temporaldistances in the graph. The other one is the temporal diameter which, looselyspeaking, is the expectation of the maximum temporal distance in the graph. Wederive the maximum expected temporal distance of a uniform random temporal stargraph as well as an upper bound on both the maximum expected temporal distanceand the temporal diameter of the normalized version of the uniform randomtemporal clique, in which the largest time-label available equals the number ofvertices. Finally, we provide an algorithm that solves an optimization problemon a specific type of temporal (multi)graphs of two vertices.
Abstract: Evolutionary dynamics have been traditionally studied in the context of homogeneous populations, mainly described by the Moran process [15]. Recently, this approach has been generalized in [13] by arranging individuals on the nodes of a network (in general, directed). In this setting, the existence of directed arcs enables the simulation of extreme phenomena, where the fixation probability of a randomly placed mutant (i.e. the probability that the offsprings of the mutant eventually spread over the whole population) is arbitrarily small or large. On the other hand, undirected networks (i.e. undirected graphs) seem to have a smoother behavior, and thus it is more challenging to find suppressors/amplifiers of selection, that is, graphs with smaller/greater fixation probability than the complete graph (i.e. the homogeneous population). In this paper we focus on undirected graphs. We present the first class of undirected graphs which act as suppressors of selection, by achieving a fixation probability that is at most one half of that of the complete graph, as the number of vertices increases. Moreover, we provide some generic upper and lower bounds for the fixation
probability of general undirected graphs. As our main contribution, we introduce the natural alternative of the model proposed in [13]. In our new evolutionary model, all individuals interact simultaneously and the result is a compromise between aggressive and non-aggressive individuals. That is, the behavior of the individuals in our new model and in the model of [13] can be interpreted as an “aggregation” vs. an “all-or-nothing” strategy, respectively. We prove that our new model of mutual influences admits a potential function, which guarantees the convergence of the system for any graph topology and any initial fitness vector of the individuals. Furthermore, we prove fast convergence to the stable state for the case of the complete graph, as well as we provide almost tight bounds on the limit fitness of the individuals. Apart from being important on its own, this new evolutionary model appears to be useful also in the abstract modeling of control mechanisms over invading populations in networks. We demonstrate this by introducing and analyzing two alternative control approaches, for which we bound the time needed to stabilize to the “healthy” state of the system.
Abstract: Motivated by the problem of efficiently collecting data from
wireless sensor networks via a mobile sink, we present an accelerated
random walk on Random Geometric Graphs. Random
walks in wireless sensor networks can serve as fully local,
very simple strategies for sink motion that significantly
reduce energy dissipation but introduce higher latency in the
data collection process. While in most cases random walks
are studied on graphs like Gn,p and Grid, we define and experimentally
evaluate our newly proposed random walk on
the Random Geometric Graphs model, that more accurately
abstracts spatial proximity in a wireless sensor network. We
call this new random walk the \~{a}-stretched random walk, and
compare it to two known random walks; its basic idea is
to favour visiting distant neighbours of the current node
towards reducing node overlap. We also define a new performance
metric called Proximity Cover Time which, along
with other metrics such as visit overlap statistics and proximity
variation, we use to evaluate the performance properties
and features of the various walks.
Abstract: The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters exploiting frequency reuse while keeping signal interference to acceptable levels. The FAP is usually modelled by variations of the graph coloring problem. The Radiocoloring (RC) of a graph G(V,E) is an assignment function Φ: V → IN such that ¦Φ(u)-Φ(v)≥ 2, when u; v are neighbors in G, and ¦Φ(u)-Φ(v)≥1 when the minimum distance of u; v in G is two. The discrete number and the range of frequencies used are called order and span, respectively. The optimization versions of the Radiocoloring Problem (RCP) are to minimize the span or the order. In this paper we prove that the min span RCP is NP-complete for planar graphs. Next, we provide an O(nΔ) time algorithm (¦V¦ = n) which obtains a radiocoloring of a planar graph G that approximates the minimum order within a ratio which tends to 2 (where Δ the maximum degree of G). Finally, we provide a fully polynomial randomized approximation scheme (fpras) for the number of valid radiocolorings of a planar graph G with λ colors, in the case λ ≥ 4λ + 50.
Abstract: It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5-regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5-regular graph is asymptotically almost surely equal to 3, provided a certain four-variable function has a unique maximum at a given point in
a bounded domain. We also describe extensive numerical evidence that strongly suggests that the latter condition holds. The proof applies the small subgraph conditioning method to the number of locally rainbow balanced 3-colorings, where a coloring is balanced if the number of vertices of each color is equal, and locally rainbow if every vertex is adjacent to at least one vertex of each of the other colors.
Abstract: Random Intersection Graphs is a new class of randomgraphs introduced in [5], in which each of n vertices randomly and independently chooses some elements from a universal set, of cardinality m. Each element is chosen with probability p. Two vertices are joined by an edge iff their chosen element sets intersect. Given n, m so that m=n{\'a}, for any real {\'a} different than one, we establish here, for the first time, tight lower bounds p0(n,m), on the value of p, as a function of n and m, above which the graph Gn,m,p is almost certainly Hamiltonian, i.e. it contains a Hamilton Cycle almost certainly. Our bounds are tight in the sense that when p is asymptotically smaller than p0(n,m) then Gn,m,p almost surely has a vertex of degree less than 2. Our proof involves new, nontrivial, coupling techniques that allow us to circumvent the edge dependencies in the random intersection model. Interestingly, Hamiltonicity appears well below the general thresholds, of [4], at which Gn,m,p looks like a usual randomgraph. Thus our bounds are much stronger than the trivial bounds implied by those thresholds.
Our results strongly support the existence of a threshold for Hamiltonicity in Gn,m,p.
Abstract: In the uniform random intersection graphs model, denoted by Gn;m;, to each vertex v
we assign exactly randomly chosen labels of some label set M of m labels and we connect every
pair of vertices that has at least one label in common. In this model, we estimate the independence
number (Gn;m;), for the wide, interesting range m = n; < 1 and = O(m1=4). We also prove
the hamiltonicity of this model by an interesting combinatorial construction. Finally, we give a brief
note concerning the independence number of Gn;m;p random intersection graphs, in which each vertex
chooses labels with probability p.
Abstract: For various random constraint satisfaction problems there is a significant gap between the largest constraint density
for which solutions exist and the largest density for which any polynomial time algorithm is known to find
solutions. Examples of this phenomenon include random k-SAT, randomgraph coloring, and a number of other
random Constraint Satisfaction Problems. To understand this gap, we study the structure of the solution space of
random k-SAT (i.e., the set of all satisfying assignments viewed as a subgraph of the Hamming cube). We prove
that for densities well below the satisfiability threshold, the solution space decomposes into an exponential number
of connected components and give quantitative bounds for the diameter, volume and number.
Abstract: For various random constraint satisfaction problems there is a significant gap between
the largest constraint density for which solutions exist and the largest density for which any polynomial
time algorithm is known to find solutions. Examples of this phenomenon include random
k-SAT, randomgraph coloring, and a number of other random constraint satisfaction problems. To
understand this gap, we study the structure of the solution space of random k-SAT (i.e., the set of
all satisfying assignments viewed as a subgraph of the Hamming cube). We prove that for densities
well below the satisfiability threshold, the solution space decomposes into an exponential number of
connected components and give quantitative bounds for the diameter, volume, and numb
Abstract: We study the on-line versions of two fundamental graph problems, maximum independent set and minimum coloring, for the case of disk graphs which are graphs resulting from intersections of disks on the plane. In particular, we investigate whether randomization can be used to break known lower bounds for deterministic on-line independent set algorithms and present new upper and lower bounds; we also present an improved upper bound for on-line coloring.
Abstract: In this work we extend the population protocol model of Angluin et al., in
order to model more powerful networks of very small resource limited
artefacts (agents) that is possible to follow some unpredictable passive
movement. These agents communicate in pairs according to the commands of
an adversary scheduler. A directed (or undirected) communication graph
encodes the following information: each edge (u,\~{o}) denotes that during the
computation it is possible for an interaction between u and \~{o} to happen in
which u is the initiator and \~{o} the responder. The new characteristic of
the proposed mediated population protocol model is the existance of a
passive communication provider that we call mediator. The mediator is a
simple database with communication capabilities. Its main purpose is to
maintain the permissible interactions in communication classes, whose
number is constant and independent of the population size. For this reason
we assume that each agent has a unique identifier for whose existence the
agent itself is not informed and thus cannot store it in its working
memory. When two agents are about to interact they send their ids to the
mediator. The mediator searches for that ordered pair in its database and
if it exists in some communication class it sends back to the agents the
state corresponding to that class. If this interaction is not permitted to
the agents, or, in other words, if this specific pair does not exist in
the database, the agents are informed to abord the interaction. Note that
in this manner for the first time we obtain some control on the safety of
the network and moreover the mediator provides us at any time with the
network topology. Equivalently, we can model the mediator by communication
links that are capable of keeping states from a edge state set of constant
cardinality. This alternative way of thinking of the new model has many
advantages concerning the formal modeling and the design of protocols,
since it enables us to abstract away the implementation details of the
mediator. Moreover, we extend further the new model by allowing the edges
to keep readable only costs, whose values also belong to a constant size
set. We then allow the protocol rules for pairwise interactions to modify
the corresponding edge state by also taking into account the costs. Thus,
our protocol descriptions are still independent of the population size and
do not use agent ids, i.e. they preserve scalability, uniformity and
anonymity. The proposed Mediated Population Protocols (MPP) can stably
compute graph properties of the communication graph. We show this for the
properties of maximal matchings (in undirected communication graphs), also
for finding the transitive closure of directed graphs and for finding all
edges of small cost. We demonstrate that our mediated protocols are
stronger than the classical population protocols. First of all we notice
an obvious fact: the classical model is a special case of the new model,
that is, the new model can compute at least the same things with the
classical one. We then present a mediated protocol that stably computes
the product of two nonnegative integers in the case where G is complete
directed and connected. Such kind of predicates are not semilinear and it
has been proven that classical population protocols in complete graphs can
compute precisely the semilinear predicates, thus in this manner we show
that there is at least one predicate that our model computes and which the
classical model cannot compute. To show this fact, we state and prove a
general Theorem about the composition of two mediated population
protocols, where the first one has stabilizing inputs. We also show that
all predicates stably computable in our model are (non-uniformly) in the
class NSPACE(m), where m is the number of edges of the communication
graph. Finally, we define Randomized MPP and show that, any Peano
predicate accepted by a Randomized MPP, can be verified in deterministic
polynomial time.
Abstract: The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters, by exploiting frequency reuse while keeping signal interference to acceptable levels. The FAP is usually modelled by variations of the graph coloring problem. A Radiocoloring (RC) of a graph G(V,E) is an assignment function View the MathML source such that |{\"O}(u)-{\"O}(v)|greater-or-equal, slanted2, when u,v are neighbors in G, and |{\"O}(u)-{\"O}(v)|greater-or-equal, slanted1 when the distance of u,v in G is two. The number of discrete frequencies and the range of frequencies used are called order and span, respectively. The optimization versions of the Radiocoloring Problem (RCP) are to minimize the span or the order. In this paper we prove that the radiocoloring problem for general graphs is hard to approximate (unless NP=ZPP) within a factor of n1/2-{\aa} (for any View the MathML source), where n is the number of vertices of the graph. However, when restricted to some special cases of graphs, the problem becomes easier. We prove that the min span RCP is NP-complete for planar graphs. Next, we provide an O(n{\"A}) time algorithm (|V|=n) which obtains a radiocoloring of a planar graph G that approximates the minimum order within a ratio which tends to 2 (where {\"A} the maximum degree of G). Finally, we provide a fully polynomial randomized approximation scheme (fpras) for the number of valid radiocolorings of a planar graph G with {\"e} colors, in the case where {\"e}greater-or-equal, slanted4{\"A}+50.
Abstract: The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters, by exploiting frequency reuse while keeping signal interference to acceptable levels. The FAP is usually modelled by variations of the graph coloring problem. A Radiocoloring (RC) of a graph G(V,E) is an assignment function View the MathML source such that |{\"O}(u)-{\"O}(v)|greater-or-equal, slanted2, when u,v are neighbors in G, and |{\"O}(u)-{\"O}(v)|greater-or-equal, slanted1 when the distance of u,v in G is two. The number of discrete frequencies and the range of frequencies used are called order and span, respectively. The optimization versions of the Radiocoloring Problem (RCP) are to minimize the span or the order. In this paper we prove that the radiocoloring problem for general graphs is hard to approximate (unless NP=ZPP) within a factor of n1/2-{\aa} (for any View the MathML source), where n is the number of vertices of the graph. However, when restricted to some special cases of graphs, the problem becomes easier. We prove that the min span RCP is NP-complete for planar graphs. Next, we provide an O(n{\"A}) time algorithm (|V|=n) which obtains a radiocoloring of a planar graph G that approximates the minimum order within a ratio which tends to 2 (where {\"A} the maximum degree of G). Finally, we provide a fully polynomial randomized approximation scheme (fpras) for the number of valid radiocolorings of a planar graph G with {\"e} colors, in the case where {\"e}greater-or-equal, slanted4{\"A}+50.
Abstract: In this work we present an efficient algorithm which, with high probability, provides
an almost uniform sample from the set of proper $\chi$-colourings of an instance of sparse
randomgraphs $G_{n,d/n}$, where $\chi=\chi(d)$ is a sufficiently large constant.
This work improves, asymptotically, the result of Dyer, Flaxman Frieze and Vigoda
in \cite{previous-result} where the algorithm proposed there needs at least
$\Theta(\frac{\log \log n}{\log \log \log n})$ colours.
Abstract: We study the on-line version of the maximum independent set problem, for the case of disk graphs which are graphs resulting
from intersections of disks on the plane. In particular, we investigate whether randomization can be used to break known lower
bounds for deterministic on-line independent set algorithms and present new upper and lower bounds.
Abstract: We investigate here the problem
of establishing communication in an ad-hoc
mobile network, that is, we assume the extreme case
of a total absence of any fixed network infrastructure
(for example a case of rapid deployment of a set of
mobile hosts in an unknown terrain). We propose, in
such a case, that a small
subset of the deployed hosts (which we call the support)
should be used to manage network operations.
However, the vast majority
of the hosts are moving arbitrarily according
to application needs.
We then provide a simple, correct and efficient protocol
for communication establishment
that avoids message flooding.
Our protocol manages to establish communication between
any pair of mobile hosts in small, a-priori
guaranteed time bounds even in the worst case of arbitrary motions of the hosts that do not belong to
the support (provided that they do not deliberately try
to avoid the support).
These time bounds, interestingly, do not depend,
on the number of mobile hosts that do not
belong in the support. They depend only on the size of the area
of motions.
Our protocol can be implemented
in very efficient ways by exploiting knowledge of the space of motions
or by adding more power to the hosts of the support.
Our results exploit and further develop some
fundamental properties of random walks in finite graphs.
Abstract: Random Intersection Graphs, Gn,m,p, is a class of randomgraphs introduced in Karoński (1999) [7] where each of the n vertices chooses independently a random subset of a universal set of m elements. Each element of the universal sets is chosen independently by some vertex with probability p. Two vertices are joined by an edge iff their chosen element sets intersect. Given n, m so that m=left ceilingn{\'a}right ceiling, for any real {\'a} different than one, we establish here, for the first time, a sharp threshold for the graph property “Contains a Hamilton cycle”. Our proof involves new, nontrivial, coupling techniques that allow us to circumvent the edge dependencies in the random intersection graph model.
Abstract: In this work we consider the problem of finding Hamilton Cycles in graphs derived from the uniform random intersection graphs model $G_{n, m, p}$. In particular, (a) for the case $m = n^{\alpha}, \alpha>1$ we give a result that allows us to apply (with the same probability of success) any algorithm that finds a Hamilton cycle with high probability in a $G_{n, k}$ graph (i.e. a graph chosen equiprobably form the space of all graphs with $k$ edges), (b) we give an \textbf{expected polynomial time} algorithm for the case $p = \textrm{constant}$ and $m \leq \alpha \sqrt{\frac{n}{\log{n}}}$ for some constant $\alpha$, and (c) we show that the greedy approach still works well even in the case $m = o(\frac{n}{\log{n}})$ and $p$ just above the connectivity threshold of $G_{n, m, p}$ (found in \cite{Singerphd}) by giving a greedy algorithm that finds a Hamilton cycle in those ranges of $m, p$ with high probability.
Abstract: In this work, we study protocols (i.e. distributed algorithms) so that populations of distributed processes can construct networks. In order to highlight the basic principles of distributed network construction we keep the model minimal in all respects. In particular, we assume finite-state processes that all begin from the same initial state and all execute the same protocol (i.e. the system is homogeneous). Moreover, we assume pairwise interactions between the processes that are scheduled by an adversary. The only constraint on the adversary scheduler is that it must be fair, intuitively meaning that it must assign to every reachable configuration of the system a non-zero probability to occur. In order to allow processes to construct networks, we let them activate and deactivate their pairwise connections. When two processes interact, the protocol takes as input the states of the processes and the state of their connection and updates all of them. In particular, in every interaction, the protocol may activate an inactive connection, deactivate an active one, or leave the state of a connection unchanged. Initially all connections are inactive and the goal is for the processes, after interacting and activating/deactivating connections for a while, to end up with a desired stable network (i.e. one that does not change any more). We give protocols (optimal in some cases) and lower bounds for several basic network construction problems such as spanning line, spanning ring, spanning star, and regular network. We provide proofs of correctness for all of our protocols and analyze the expected time to convergence of most of them under a uniform random scheduler that selects the next pair of interacting processes uniformly at random from all such pairs. Finally, we prove several universality results by presenting generic protocols that are capable of simulating a Turing Machine (TM) and exploiting it in order to construct a large class of networks. Our universality protocols use a subset of the population (waste) in order to distributedly construct there a TM able to decide a graph class in some given space. Then, the protocols repeatedly construct in the rest of the population (useful space) a graph equiprobably drawn from all possible graphs. The TM works on this and accepts if the presented graph is in the class. We additionally show how to partition the population into k supernodes, each being a line of log k nodes, for the largest such k. This amount of local memory is sufficient for the supernodes to obtain unique names and exploit their names and their memory to realize nontrivial constructions. Delicate composition and reinitialization issues have to be solved for these general constructions to work.
Abstract: We address an important communication issue in wireless cellular networks that utilize Frequency Division Multiplexing (FDM) technology. In such networks, many users within the same geographical region (cell) can communicate simultaneously with other users of the network using distinct frequencies. The spectrum of the available frequencies is limited; thus, efficient solutions to the call control problem are essential. The objective of the call control problem is, given a spectrum of available frequencies and users that wish to communicate, to maximize the number of users that communicate without signal interference. We consider cellular networks of reuse distance kge 2 and we study the on-line version of the problem using competitive analysis.
In cellular networks of reuse distance 2, the previously best known algorithm that beats the lower bound of 3 on the competitiveness of deterministic algorithms works on networks with one frequency, achieves a competitive ratio against oblivious adversaries which is between 2.469 and 2.651, and uses a number of random bits at least proportional to the size of the network. We significantly improve this result by presenting a series of simple randomized algorithms that have competitive ratios smaller than 3, work on networks with arbitrarily many frequencies, and use only a constant number of random bits or a comparable weak random source. The best competitiveness upper bound we obtain is 7/3.
In cellular networks of reuse distance k>2, we present simple randomized on-line call control algorithms with competitive ratios which significantly beat the lower bounds on the competitiveness of deterministic ones and use only random bits. Furthermore, we show a new lower bound on the competitiveness of on-line call control algorithms in cellular networks of reuse distance kge 5.
Abstract: We generalize Cuckoo Hashing [16] to d-ary Cuckoo Hashing and show how this yields a simple hash table data structure that stores n elements in (1 + ∈) n memory cells, for any constant ∈ > 0. Assuming uniform hashing, accessing or deleting table entries takes at most d = O(ln 1/∈ ) probes and the expected amortized insertion time is constant. This is the first dictionary that has worst case constant access time and expected constant update time, works with (1+∈) n space, and supports satellite information. Experiments indicate that d = 4 choices suffice for ∈ ≈ 0.03. We also describe a hash table data structure using explicit constant time hash functions, using at most d = O(ln2 1/∈ ) probes in the worst case.
A corollary is an expected linear time algorithm for finding maximum cardinality matchings in a rather natural model of sparse random bipartite graphs.
This work was partially supported by DFG grant SA 933/1-1 and the Future and Emerging Technologies programme of the EU under contract number IST-1999- 14186 (ALCOM-FT).
The present work was initiated while this author was at BRICS, Aarhus University, Denmark.
Part of this work was done while the author was at MPII. 1 In this paper “whp.” will mean “with probability 1 - O(1/n)”.
Abstract: We generalize Cuckoo Hashing [16] to d-ary Cuckoo Hashing and show how this yields a simple hash table data structure that stores n elements in (1 + ∈) n memory cells, for any constant ∈ > 0. Assuming uniform hashing, accessing or deleting table entries takes at most d = O(ln 1/∈ ) probes and the expected amortized insertion time is constant. This is the first dictionary that has worst case constant access time and expected constant update time, works with (1+∈) n space, and supports satellite information. Experiments indicate that d = 4 choices suffice for ∈ ≈ 0.03. We also describe a hash table data structure using explicit constant time hash functions, using at most d = O(ln2 1/∈ ) probes in the worst case.
A corollary is an expected linear time algorithm for finding maximum cardinality matchings in a rather natural model of sparse random bipartite graphs.
This work was partially supported by DFG grant SA 933/1-1 and the Future and Emerging Technologies programme of the EU under contract number IST-1999- 14186 (ALCOM-FT).
The present work was initiated while this author was at BRICS, Aarhus University, Denmark.
Part of this work was done while the author was at MPII. 1 In this paper “whp.” will mean “with probability 1 - O(1/n)”.
Abstract: This work extends what is known so far for a basic model of
evolutionary antagonis
m in undirected ne
tworks (graphs).
More specif-
ically, this work studies the generalized Moran process, as introduced
by Lieberman, Hauert, and Nowak [Nature, 433:312-316, 2005], where
the individuals of a population reside on the vertices of an undirected
connected graph. The initial population has a single
mutant
of a
fitness
value
r
(typically
r>
1), residing at some vertex
v
of the graph, while
every other vertex is initially occupied by an individual of fitness 1. At
every step of this process, an individual (i.e. vertex) is randomly chosen
for reproduction with probability proportional to its fitness, and then it
places a copy of itself on a random neighbor, thus replacing the individ-
ual that was residing there. The main quantity of interest is the
fixation
probability
, i.e. the probability that eventually the whole graph is occu-
pied by descendants of the mutant. In this work we concentrate on the
fixation probability when the mutant is initially on a specific vertex
v
,
thus refining the older notion of Lieberman et al. which studied the fix-
ation probability when the initial mutant is placed at a random vertex.
We then aim at finding graphs that have many “strong starts” (or many
“weak starts”) for the mutant. Thus we introduce a parameterized no-
tion of
selective amplifiers
(resp.
selective suppressors
)ofevolution.We
prove the existence of
strong
selective amplifiers (i.e. for
h
(
n
)=
Θ
(
n
)
vertices
v
the fixation probability of
v
is at least 1
−
c
(
r
)
n
for a func-
tion
c
(
r
) that depends only on
r
), and the existence of quite strong
selective suppressors. Regarding the traditional notion of fixation prob-
ability from a random start, we provi
de strong upper and lower bounds:
first we demonstrate the non-existence of “strong universal” amplifiers,
and second we prove the
Thermal Theorem
which states that for any
undirected graph, when the mutant starts at vertex
v
, the fixation prob-
ability at least (
r
−
1)
/
(
r
+
deg
v
deg
min
). This theorem (which extends the
“Isothermal Theorem” of Lieberman et al. for regular graphs) implies
an almost tight lower bound for the usual notion of fixation probability.
Our proof techniques are original and are based on new domination ar-
guments which may be of general interest in Markov Processes that are
of the general birth-death type.
Abstract: Random scaled sector graphs were introduced as a generalization of random geometric graphs to model networks of sensors using optical communication. In the random scaled sector graph model vertices are placed uniformly at random into the [0, 1]2 unit square. Each vertex i is assigned uniformly at random sector Si, of central angle {\'a}i, in a circle of radius ri (with vertex i as the origin). An arc is present from vertex i to any vertex j, if j falls in Si. In this work, we study the value of the chromatic number ƒ{\^O}(Gn), directed clique number {\`u}(Gn), and undirected clique number {\`u}2 (Gn) for random scaled sector graphs with n vertices, where each vertex spans a sector of {\'a} degrees with radius rn = \~{a}ln n/n. We prove that for values {\'a} < ƒ{\^I}, as n ¨ ‡ w.h.p., ƒ{\^O}(Gn) and {\`u}2 (Gn) are {\`E}(ln n/ln ln n), while {\`u}(Gn) is O(1), showing a clear difference with the random geometric graph model. For {\'a} > ƒ{\^I} w.h.p., ƒ{\^O}(Gn) and {\`u}2 (Gn) are {\`E} (ln n), being the same for random scaled sector and random geometric graphs, while {\`u}(Gn) is {\`E}(ln n/ln ln n).
Abstract: We investigate the existence and efficient algorithmic construction
of close to optimal independent sets in random models of intersection
graphs. In particular, (a) we propose a new model for random
intersection graphs (Gn,m,p) which includes the model of [10] (the “uniform”
random intersection graphs model) as an important special case.
We also define an interesting variation of the model of random intersection
graphs, similar in spirit to random regular graphs. (b) For this
model we derive exact formulae for the mean and variance of the number
of independent sets of size k (for any k) in the graph. (c) We then propose
and analyse three algorithms for the efficient construction of large
independent sets in this model. The first two are variations of the greedy
technique while the third is a totally new algorithm. Our algorithms are
analysed for the special case of uniform random intersection graphs.
Our analyses show that these algorithms succeed in finding close to optimal
independent sets for an interesting range of graph parameters.
Abstract: We investigate the existence and efficient algorithmic construction of close to opti-
mal independent sets in random models of intersection graphs. In particular, (a) we
propose a new model for random intersection graphs (Gn,m,~p) which includes the
model of [10] (the “uniform” random intersection graphs model) as an important
special case. We also define an interesting variation of the model of random intersec-
tion graphs, similar in spirit to random regular graphs. (b) For this model we derive
exact formulae for the mean and variance of the number of independent sets of size
k (for any k) in the graph. (c) We then propose and analyse three algorithms for
the efficient construction of large independent sets in this model. The first two are
variations of the greedy technique while the third is a totally new algorithm. Our
algorithms are analysed for the special case of uniform random intersection graphs.
Our analyses show that these algorithms succeed in finding close to optimal in-
dependent sets for an interesting range of graph parameters.
Abstract: Consider k particles, 1 red and k-1 white, chasing each other on the nodes of a graph G. If the red one catches one of the white, it “infects” it with its color. The newly red particles are now available to infect more white ones. When is it the case that all white will become red? It turns out that this simple question is an instance of information propagation between random walks and has important applications to mobile computing where a set of mobile hosts acts as an intermediary for the spread of information.
In this paper we model this problem by k concurrent random walks, one corresponding to the red particle and k-1 to the white ones. The infection time Tk of infecting all the white particles with red color is then a random variable that depends on k, the initial position of the particles, the number of nodes and edges of the graph, as well as on the structure of the graph.
In this work we develop a set of probabilistic tools that we use to obtain upper bounds on the (worst case w.r.t. initial positions of particles) expected value of Tk for general graphs and important special cases. We easily get that an upper bound on the expected value of Tk is the worst case (over all initial positions) expected meeting time m* of two random walks multiplied by . We demonstrate that this is, indeed, a tight bound; i.e. there is a graph G (a special case of the “lollipop” graph), a range of values kgraphs are tight.
Abstract: We consider a strategic game with two classes of confronting
randomized players on a graph G(V,E): {\'i} attackers, each choosing vertices
and wishing to minimize the probability of being caught, and a
defender, who chooses edges and gains the expected number of attackers
it catches. The Price of Defense is the worst-case ratio, over all Nash
equilibria, of the optimal gain of the defender over its gain at a Nash equilibrium.
We provide a comprehensive collection of trade-offs between the
Price of Defense and the computational efficiency of Nash equilibria.
– Through reduction to a Two-Players, Constant-Sum Game, we prove
that a Nash equilibrium can be computed in polynomial time. The
reduction does not provide any apparent guarantees on the Price of
Defense.
– To obtain such, we analyze several structured Nash equilibria:
• In a Matching Nash equilibrium, the support of the defender is
an Edge Cover. We prove that they can be computed in polynomial
time, and they incur a Price of Defense of {\'a}(G), the
Independence Number of G.
• In a Perfect Matching Nash equilibrium, the support of the defender
is a Perfect Matching. We prove that they can be computed
in polynomial time, and they incur a Price of Defense of
|V |
2 .
• In a Defender Uniform Nash equilibrium, the defender chooses
uniformly each edge in its support. We prove that they incur a
Price of Defense falling between those for Matching and Perfect
Matching Nash Equilibria; however, it is NP-complete to decide
their existence.
• In an Attacker Symmetric and Uniform Nash equilibrium, all
attackers have a common support on which each uses a uniform
distribution. We prove that they can be computed in polynomial
time and incur a Price of Defense of either
|V |
2 or {\'a}(G).
Abstract: Consider a network vulnerable to security attacks and equipped with defense mechanisms. How much is the loss in the provided security guarantees due to the selfish nature of attacks and defenses? The Price of Defense was recently introduced in [7] as a worst-case measure, over all associated Nash equilibria, of this loss. In the particular strategic game considered in [7], there are two classes of confronting randomized players on a graph G(V,E): v attackers, each choosing vertices and wishing to minimize the probability of being caught, and a single defender, who chooses edges and gains the expected number of attackers it catches. In this work, we continue the study of the Price of Defense. We obtain the following results: - The Price of Defense is at least |V| 2; this implies that the Perfect Matching Nash equilibria considered in [7] are optimal with respect to the Price of Defense, so that the lower bound is tight. - We define Defense-Optimal graphs as those admitting a Nash equilibrium that attains the (tight) lower bound of |V| 2. We obtain: › A graph is Defense-Optimal if and only if it has a Fractional Perfect Matching. Since graphs with a Fractional Perfect Matching are recognizable in polynomial time, the same holds for Defense-Optimal graphs. › We identify a very simple graph that is Defense-Optimal but has no Perfect Matching Nash equilibrium. - Inspired by the established connection between Nash equilibria and Fractional Perfect Matchings, we transfer a known bivaluedness result about Fractional Matchings to a certain class of Nash equilibria. So, the connection to Fractional Graph Theory may be the key to revealing the combinatorial structure of Nash equilibria for our network security game.
Abstract: In this paper we examine spectral properties of random intersection graphs when the number of vertices is equal to the number of labels. We call this class symmetric random intersection graphs. We examine symmetric random intersection graphs when the probability that a vertex selects a label is close to the connectivity threshold $\tau_c$. In particular, we examine the size of the second eigenvalue of the transition matrix corresponding to the Markov Chain that describes a random walk on an instance of the symmetric random intersection graph $G_{n, n, p}$. We show that with high probability the second eigenvalue is upper bounded by some constant $\zeta < 1$.
Abstract: In this paper we examine spectral properties of random intersection graphs when the number
of vertices is equal to the number of labels. We call this class symmetric random intersection graphs.
We examine symmetric random intersection graphs when the probability that a vertex selects a label
is close to the connectivity threshold ¿c. In particular, we examine the size of the second eigenvalue of
the transition matrix corresponding to the Markov Chain that describes a random walk on an instance
of the symmetric random intersection graph Gn,n,p. We show that with high probability the second
eigenvalue is upper bounded by some constant ³ < 1.
Abstract: We study here dynamic antagonism in a fixed network, represented as a graph $G$ of $n$ vertices. In particular, we consider the case of $k \leq n$ particles walking randomly independently around the network. Each particle belongs to exactly one of two antagonistic species, none of which can give birth to children. When two particles meet, they are engaged in a (sometimes mortal) local fight. The outcome of the fight depends on the species to which the particles belong. Our problem is \emph{to predict} (i.e. to compute) the eventual chances of species survival. We prove here that this can indeed be done in \emph{expected polynomial time on the size of the network}, provided that the network is \emph{undirected}.
Abstract: In this paper we study the threshold behavior of the fixed radius randomgraph model and its applications to the key management problem of sensor networks and, generally, for mobile ad-hoc networks. We show that this randomgraph model can realistically model the placement of nodes within a certain region and their interaction/sensing capabilities (i.e. transmission range, light sensing sensitivity etc.). We also show that this model can be used to define key sets for the network nodes that satisfy a number of good properties, allowing to set up secure communication with each other depending on randomly created sets of keys related to their current location. Our work hopes to inaugurate a study of key management schemes whose properties are related to properties of an appropriate randomgraph model and, thus, use the rich theory developed in the randomgraph literature in order to transfer ?good? properties of the graph model to the key sets of the nodes.
Partially supported by the IST Programme of the European Union under contact number IST-2005-15964 (AEOLUS) and the INTAS Programme under contract with Ref. No 04-77-7173 (Data Flow Systems: Algorithms and Complexity (DFS-AC)).
Abstract: We study the existence and tractability of a notion of approximate
equilibria in bimatrix games, called well supported approximate
Nash Equilibria (SuppNE in short).We prove existence of "−SuppNE for
any constant " 2 (0, 1), with only logarithmic support sizes for both players.
Also we propose a polynomial–time construction of SuppNE, both
for win lose and for arbitrary (normalized) bimatrix games. The quality
of these SuppNE depends on the girth of the Nash Dynamics graph in
the win lose game, or a (rounded–off) win lose image of the original normalized
game. Our constructions are very successful in sparse win lose
games (ie, having a constant number of (0, 1)−elements in the bimatrix)
with large girth in the Nash Dynamics graph. The same holds also for
normalized games whose win lose image is sparse with large girth.
Finally we prove the simplicity of constructing SuppNE both in random
normalized games and in random win lose games. In the former case we
prove that the uniform full mix is an o(1)−SuppNE, while in the case
of win lose games, we show that (with high probability) there is either a
PNE or a 0.5-SuppNE with support sizes only 2.
Abstract: Motivated by the problem of efficient sensor network data collection via a mobile sink, we present undergoing research in accelerated random walks on Random Geometric Graphs. We first propose a new type of random walk, called the {\'a}-stretched random walk, and compare it to three known random walks. We also define a novel performance metric called Proximity Cover Time which, along with other metrics such us visit overlap statistics and proximity variation, we use to evaluate the performance properties and features of the various walks. Finally, we present future plans on investigating a relevant combinatorial property of Random Geometric Graphs that may lead to new, faster random walks and metrics.