Concept

Cluster graph

Publications associées (9)

Motif Cut Sparsifiers

Mikhail Kapralov, Mikhail Makarov, Jakab Tardos

A motif is a frequently occurring subgraph of a given directed or undirected graph G (Milo et al.). Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clusterin ...

IEEE COMPUTER SOC2022

Representation Learning for Multi-relational Data

Eda Bayram

Recent years have witnessed a rise in real-world data captured with rich structural information that can be better depicted by multi-relational or heterogeneous graphs. However, research on relational representation learning has so far mostly focused on th ...

EPFL2021

Sublinear Algorithms for Spectral Graph Clustering

Aidasadat Mousavifar

This thesis focuses on designing spectral tools for graph clustering in sublinear time. With the emergence of big data, many traditional polynomial time, and even linear time algorithms have become prohibitively expensive. Processing modern datasets requir ...

EPFL2021

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Igor Malinovic

Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above a given threshold. While this model successfully general ...

EPFL2019

Robust and Efficient Data Clustering with Signal Processing on Graphs

Lionel Jérémie Martin

Data is pervasive in today's world and has actually been for quite some time. With the increasing volume of data to process, there is a need for faster and at least as accurate techniques than what we already have. In particular, the last decade recorded t ...

EPFL2018

The gene family-free median of three

Metin Balaban

Background: The gene family-free framework for comparative genomics aims at providing methods for gene order analysis that do not require prior gene family assignment, but work directly on a sequence similarity graph. We study two problems related to the b ...

2017

When Slepian Meets Fiedler: Putting a Focus on the Graph Spectrum

Dimitri Nestor Alice Van De Ville, Maria Giulia Preti, Robin Jonathan Demesmaeker

The study of complex systems greatly benefits from graph models and their analysis. In particular, the eigendecomposition of the graph Laplacian lets emerge properties of global organization from local interactions; e.g., the Fiedler vector has the smalles ...

IEEE Institute of Electrical and Electronics Engineers2017

Clustered planarity testing revisited

Radoslav Fulek, Jan Kyncl, Igor Malinovic

The Hanani--Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generali ...

2015

Partitioning cographs into cliques and stable sets

Dominique de Werra, Tinaz Ekim

We consider the problem of partitioning the node set of a graph into p cliques and k stable sets, namely the (p,k)-coloring problem. Results have been obtained for general graphs \cite{hellcomp}, chordal graphs \cite{hellchordal} and cacti for the case whe ...

2005