**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Lecture# Graph Sketching: Connected Components

Description

This lecture covers the concept of graph sketching with a focus on connected components. It discusses various techniques for sketching graphs and identifying connected components efficiently in streaming models. The instructor explains the process of dynamic graph streaming and adversarial order in graph streams, emphasizing the importance of maintaining connectivity in insertion-only streams.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

In course

CS-448: Sublinear algorithms for big data analysis

In this course we will define rigorous mathematical models for computing on large datasets, cover main algorithmic techniques that have been developed for sublinear (e.g. faster than linear time) data

Related concepts (119)

Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network. In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v.

Directed acyclic graph

In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called arcs), with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions.

Glossary of graph theory

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

Vertex cover

In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimization problem. It is NP-hard, so it cannot be solved by a polynomial-time algorithm if P ≠ NP. Moreover, it is hard to approximate – it cannot be approximated up to a factor smaller than 2 if the unique games conjecture is true. On the other hand, it has several simple 2-factor approximations.

SpaceX

Space Exploration Technologies Corp., doing business as SpaceX, is an American spacecraft manufacturer, launch service provider and satellite communications company headquartered in Hawthorne, California. The company was founded in 2002 by Elon Musk with the goal of reducing space transportation costs and to colonize Mars. The company manufactures the Falcon 9, Falcon Heavy and Starship heavy-lift launch vehicles, the Cargo Dragon and Crew Dragon spacecraft, the Starlink mega-constellation satellite and rocket engines.

Related lectures (627)

Graph Sketching: Connected ComponentsCS-448: Sublinear algorithms for big data analysis

Covers the concept of graph sketching with a focus on connected components.

Automorphism groups: Trees and Graphs

Explores automorphism groups in trees and graphs, focusing on ends and types of automorphisms.

Open Mapping TheoremMATH-410: Riemann surfaces

Explains the Open Mapping Theorem for holomorphic maps between Riemann surfaces.

Numerical Analysis: Implicit SchemesMATH-351: Advanced numerical analysis

Covers implicit schemes in numerical analysis for solving partial differential equations.

Differential Forms IntegrationMATH-410: Riemann surfaces

Covers the integration of differential forms on smooth manifolds, including the concepts of closed and exact forms.