Author name cluster

Sotiris E. Nikoletseas

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

1 author row

MFCS Conference 2016 Conference Paper

Stably Computing Order Statistics with Arithmetic Population Protocols

George B. Mertzios
Sotiris E. Nikoletseas
Christoforos L. Raptopoulos
Paul G. Spirakis

In this paper we initiate the study of populations of agents with very limited capabilities that are globally able to compute order statistics of their arithmetic input values via pair-wise meetings. To this extent, we introduce the Arithmetic Population Protocol (APP) model, embarking from the well known Population Protocol (PP) model and inspired by two recent papers in which states are treated as integer numbers. In the APP model, every agent has a state from a set Q of states, as well as a fixed number of registers (independent of the size of the population), each of which can store an element from a totally ordered set S of samples. Whenever two agents interact with each other, they update their states and the values stored in their registers according to a joint transition function. This transition function is also restricted; it only allows (a) comparisons and (b) copy / paste operations for the sample values that are stored in the registers of the two interacting agents. Agents can only meet in pairs via a fair scheduler and are required to eventually converge to the same output value of the function that the protocol globally and stably computes. We present two different APPs for stably computing the median of the input values, initially stored on the agents of the population. Our first APP, in which every agent has 3 registers and no states, stably computes (with probability 1) the median under any fair scheduler in any strongly connected directed (or connected undirected) interaction graph. Under the probabilistic scheduler, we show that our protocol stably computes the median in O(n^6) number of interactions in a connected undirected interaction graph of n agents. Our second APP, in which every agent has 2 registers and O(n^2 log{n}) states, computes to the correct median of the input with high probability in O(n^3 log{n}) interactions, assuming the probabilistic scheduler and the complete interaction graph. Finally we present a third APP which, for any k, stably computes the k-th smallest element of the input of the population under any fair scheduler and in any strongly connected directed (or connected undirected) interaction graph. In this APP every agent has 2 registers and n states. Upon convergence every agent has a different state; all these states provide a total ordering of the agents with respect to their input values.

Details

MFCS Conference 2012 Conference Paper

Maximum Cliques in Graphs with Small Intersection Number and Random Intersection Graphs

Sotiris E. Nikoletseas
Christoforos L. Raptopoulos
Paul G. Spirakis

Abstract In this paper, we relate the problem of finding a maximum clique to the intersection number of the input graph (i. e. the minimum number of cliques needed to edge cover the graph). In particular, we consider the maximum clique problem for graphs with small intersection number and random intersection graphs (a model in which each one of m labels is chosen independently with probability p by each one of n vertices, and there are edges between any vertices with overlaps in the labels chosen). We first present a simple algorithm which, on input G finds a maximum clique in \(O(2^{2^m + O(m)} + n^2 \min\{2^m, n\})\) time steps, where m is an upper bound on the intersection number and n is the number of vertices. Consequently, when m ≤ ln ln n the running time of this algorithm is polynomial. We then consider random instances of the random intersection graphs model as input graphs. As our main contribution, we prove that, when the number of labels is not too large ( m = n α, 0 < α < 1), we can use the label choices of the vertices to find a maximum clique in polynomial time whp. The proof of correctness for this algorithm relies on our Single Label Clique Theorem, which roughly states that whp a “large enough” clique cannot be formed by more than one label. This theorem generalizes and strengthens other related results in the state of the art, but also broadens the range of values considered (see e. g. [22] and [4]). As an important consequence of our Single Label Clique Theorem, we prove that the problem of inferring the complete information of label choices for each vertex from the resulting random intersection graph (i. e. the label representation of the graph ) is solvable whp; namely, the maximum likelihood estimation method will provide a unique solution (up to permutations of the labels). Finding efficient algorithms for constructing such a label representation is left as an interesting open problem for future research.

Details

MFCS Conference 2009 Conference Paper

Colouring Non-sparse Random Intersection Graphs

Sotiris E. Nikoletseas
Christoforos L. Raptopoulos
Paul G. Spirakis

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, 32]) 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 α for α less than 1 (in this range, RIGs differ substantially from the Erdös-Renyi random graphs) and (b) the selection probability p is quite high (e. g. at least \(\frac{\ln^2{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 \({\cal G}_{n, m, p}\), for any mp ≥ ln 2 n. The algorithm uses information of the label sets assigned to the vertices of G n, m, p and runs in \(O\left(\frac{n^2mp^2}{\ln{n}} \right)\) 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 G n, m, p. We finally compare the problem of finding a proper colouring for G n, 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 G n, m, p, for any integer k, such that no clique induced by only one label in G n, 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.

Details

MFCS Conference 2007 Conference Paper

Expander Properties and the Cover Time of Random Intersection Graphs

Sotiris E. Nikoletseas
Christoforos L. Raptopoulos
Paul G. Spirakis

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 Θ ( 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 random graphs.

Details

MFCS Conference 2002 Conference Paper

On Radiocoloring Hierarchically Specified Planar Graphs: PSPACE-Completeness and Approximations

Maria I. Andreou
Dimitris Fotakis 0001
Sotiris E. Nikoletseas
Vicky G. Papadopoulou
Paul G. Spirakis

Abstract Hierarchical specifications of graphs have been widely used in many important applications, such as VLSI design, parallel programming and software engineering. A well known hierarchical specification model, considered in this work, is that of Lengauer [ 9, 10 ] referred to as L-specifications. In this paper we discuss a restriction on the L-specifications resulting to graphs which we call Well-Separated (WS). This class is characterized by a polynomial time (to the size of the specification of the graph) testable combinatorial property. In this work we study the Radiocoloring Problem (RCP) on WS L-specified hierarchical planar graphs. The optimization version of RCP studied here, consists in assigning colors to the vertices of a graph, such that any two vertices of distance at most two get different colors. The objective here is to minimize the number of colors used. This problem is equivalent to the problem of vertex coloring the square of a graph G, G 2, where G 2 has the same vertex set as G and there is an edge between any two vertices of G 2 if their distance in G is at most 2. We first show that RCP is \( \mathcal{P}\mathcal{S}\mathcal{P}\mathcal{A}\mathcal{C}\mathcal{E} \) -complete for WS L-specified hierarchical planar graphs. Second, we present a polynomial time 3-approximation algorithm as well as a more efficient 4-approximation algorithm for RCP on graphs of this class. We note that, the best currently known approximation ratio for the RCP on ordinary (non-hierarchical) planar graphs of general degree is 2 ([ 6, 1 ]). Note also that the only known results on any kind of coloring problems have been shown for another special kind of hierarchical graphs (unit disk graphs) achieving a 6-approximation solution [ 13 ].

Details

MFCS Conference 2000 Conference Paper

NP-Completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs

Dimitris Fotakis 0001
Sotiris E. Nikoletseas
Vicky G. Papadopoulou
Paul G. Spirakis

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.

Details