Bengt J. Nilsson

Prof. Bengt J. Nilsson


Research Focus & Metrics

Academic Career Length

15Years (2012-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
6 June 2012 in Algorithmica
Verified
Journal Article
Closed access
PDF file
EKErik Krohn
Erik Krohn
BNBengt J. Nilsson
Bengt J. Nilsson

16 May 2015
Verified
Book Chapter
Closed access
PDF file
MCMarek Chrobak
Marek Chrobak
CDChristoph Dürr
Christoph Dürr
BNBengt J. Nilsson
Bengt J. Nilsson

17 October 2016 in arXiv
Verified
Preprint
Open access
PDF file
MCMarek Chrobak
Marek Chrobak
CDChristoph Durr
Christoph Durr
AFAleksander Fabijan
Aleksander Fabijan
BNBengt J. Nilsson
Bengt J. Nilsson
Clique clustering is the problem of partitioning the vertices of a graph into disjoint clusters, where each cluster forms a clique in the graph, while optimizing some objective function. In online clustering, the input graph is given one vertex at a time, and any vertices that have previously been clustered together are not allowed to be separated. The goal is to maintain a clustering with an objective value close to the optimal solution. For the variant where we want to maximize the number of edges in the clusters, we propose an online strategy based on the doubling technique. It has an asymptotic competitive ratio at most 15.646 and an absolute competitive ratio at most 22.641. We also show that no deterministic strategy can have an asymptotic competitive ratio better than 6. For the variant where we want to minimize the number of edges between clusters, we show that the deterministic competitive ratio of the problem is $n-\omega(1)$, where n is the number of vertices in the graph.