36 citations · 170 across the 60 of their papers we have counts for
7 papers · 1 filter
A spectral algorithm for finding maximum cliques in dense random intersection graphs
Filippos Christodoulou, Sotiris Nikoletseas, Christoforos Raptopoulos +1
In a random intersection graph , each of vertices selects a random subset of a set of labels by including each label independently with probability and edges…
MAX CUT in Weighted Random Intersection Graphs and Discrepancy of Sparse Random Set Systems
Sotiris Nikoletseas, Christoforos Raptopoulos, Paul Spirakis
Let be a set of vertices, a set of labels, and let be an matrix of independent Bernoulli random variables with success probability…
On the Complexity of Weighted Greedy Matchings
Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis
Motivated by the fact that in several cases a matching in a graph is stable if and only if it is produced by a greedy algorithm, we study the problem of computing a maximum weight…
The complexity of optimal design of temporally connected graphs
Eleni C. Akrida, Leszek Gasieniec, George B. Mertzios +1
We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of vertices, where each edge has an associated se…
Temporal Network Optimization Subject to Connectivity Constraints
George B. Mertzios, Othon Michail, Paul G. Spirakis
In this work we consider \emph{temporal networks}, i.e. networks defined by a \emph{labeling} assigning to each edge of an \emph{underlying graph} a set of \emph{discrete}…
Maximum Cliques in Graphs with Small Intersection Number and Random Intersection Graphs
S. Nikoletseas, C. Raptopoulos, P. G. Spirakis
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).…