Refine
Language
- English (5)
Keywords
- colouring (1)
- complex networks (1)
- intersection graphs (1)
- random graphs (1)
Project
- A5 (5)
Application Area
- A (5)
Random intersection graphs naturally exhibit a certain amount of transitivity and hence can
be used to model real--world networks. We study the evolution of the chromatic number
of a random intersection graph and show that, in a certain range of parameters,
these random graphs can be coloured optimally with high probability using different greedy
algorithms.
Experiments on real network data confirm the positive theoretical predictions and
suggest that heuristics for the clique and the chromatic number can work hand in hand
proving mutual optimality.
We investigate the problem of colouring random graphs G ? G(n; p)
in polynomial expected time. For the case p ? 1.01/n, we present an algorithm
that finds an optimal colouring in linear expected time. For
p ?? ln6(n)/n, we give algorithms which approximate the chromatic
number within a factor of O(? np). We also obtain an O(?
np/ ln(np))-
approximation algorithm for the independence number. As an application,
we propose an algorithm for deciding satisfiability of random 2k-
SAT formulas (with sufficiently many clauses) in
polynomial expected time.
We investigate the problem of colouring random graphs G ? G(n, p) in polynomial expected time. For the case p < 1.01/n, we present an algorithm that finds an optimal colouring in linear expected time. For suficiently large values of p, we give algorithms which approximate the chromatic number within a factor of O(?np). As a byproduct, we obtain an O(?np/ ln(np))-approximation algorithm for the independence number which runs in polynomial expected time provided p ? ln6 n/n.
We prove sufficient and essentially necessary conditions in terms of the
minimum degree for a graph to contain planar subgraphs with many edges.
For example, for all positive γ every sufficiently large graph G with minimum
degree at least (2/3 + γ)|G| contains a triangulation as a spanning
subgraph, whereas this need not be the case when the minimum degree is
less than 2|G|/3.