Celebrity

In the context of computer science, „Celebrity“ refers to a specific problem within graph theory, particularly in the study of social networks and algorithms. The Celebrity problem is defined within a group of people where each person may or may not know each other. The main question is to determine if there is a „celebrity“ in the group—someone who is known by everyone else but who does not know anyone in return.

Mathematically, this can be represented as a directed graph where nodes represent individuals and directed edges indicate knowledge of one another (an edge from A to B suggests A knows B). A celebrity must satisfy two conditions: they are known by all other members of the group, and they do not know any of the members themselves.

The problem can be solved efficiently using various algorithms and is often used to illustrate search and identification techniques in graph theory. Recognizing a celebrity, if one exists, can typically be done in linear time relative to the number of people due to the properties of directed graphs.