Category Graph Algorithms
Maintaining a random sample of edges on a dynamic graph
Suppose that we have a sample of edges, sampled uniformly at random from the edge set of a graph . Also, let . Now the graph changes, in particular, either a non-existing edge (if the graph is not complete) is inserted or an existing edge is deleted. Do we need to sample edges from scratch?More generally, […]
k-clique densest subgraph problem
Motivation: Suppose you are given a large “who-calls-whom” network. This is a network where each vertex represents a human and we have an (undirected) edge between two humans if and only if they exchanged a phone call. An important problem that comes up in anomaly detection is finding sets of vertices that “look like” cliques. […]
Giant component with Depth First Search
I just finished reading a short paper of Michael Krivelevich and Benny Sudakov, two leading experts in probabilistic combinatorics, which appeared in Arxiv about a month ago [1]. It is a simple proof of the classical result that the random binomial graph exhibits a phase transition around . When then the largest component has size […]
tsourakakis.com 