Concept

Line graph

Related publications (541)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

EPFL2019

Distributed Coloring of Graphs with an Optimal Number of Colors

Etienne Michel François Bamas

This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs optimally (i.e. with the minimum number of colors) in the LOCAL model of computation. Most of the work on distributed vertex coloring so far has focused on ...

SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS2019

Graph-based image representation learning

Renata Khasanova

Though deep learning (DL) algorithms are very powerful for image processing tasks, they generally require a lot of data to reach their full potential. Furthermore, there is no straightforward way to impose various properties, given by the prior knowledge a ...

EPFL2019

Local Approximation of the Maximum Cut in Regular Graphs

Etienne Michel François Bamas

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and ...

SPRINGER INTERNATIONAL PUBLISHING AG2019

Network Alignment by Representation Learning on Structure and Attribute

Thanh Trung Huynh, Quoc Viet Hung Nguyen, Thành Tâm Nguyên, Chi Thang Duong

Network alignment is the task of recognizing similar network nodes across different networks, which has many applications in various domains. As traditional network alignment methods based on matrix factorization do not scale to large graphs, a variety of ...

SPRINGER INTERNATIONAL PUBLISHING AG2019

Graph Laplacians for Rotation Equivariant Convolutional Neural Networks

Martino Milani

A fundamental problem in signal processing is to design computationally efficient algorithms to filter signals. In many applications, the signals to filter lie on a sphere. Meaningful examples of data of this kind are weather data on the Earth, or images o ...

2019

Weighted Matchings via Unweighted Augmentations

Ola Nils Anders Svensson, Slobodan Mitrovic, Buddhima Ruwanmini Gamlath Gamlath Ralalage

We design a generic method to reduce the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide efficient implementations for approximating weighted matchings in the massively pa ...

ASSOC COMPUTING MACHINERY2019

MyDEP: A New Computational Tool for Dielectric Modeling of Particles and Cells

Philippe Renaud, Jonathan Bastien Cottet

Dielectrophoresis (DEP) and electrorotation (ROT) are two electrokinetic phenomena exploiting nonuniform electric fields to exert a force or torque on biological particles suspended in liquid media. They are widely used in lab-on-chip devices for the manip ...

2019

Thrackles: An improved upper bound

János Pach, Radoslav Fulek

A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, ex ...

ELSEVIER SCIENCE BV2019

Fourier could be a data scientist: From graph Fourier transform to signal processing on graphs

Pierre Vandergheynst, Benjamin Ricaud, Nicolas Tremblay

The legacy of Joseph Fourier in science is vast, especially thanks to the essential tool that the Fourier transform is. The flexibility of this analysis, its computational efficiency and the physical interpretation it offers makes it a cornerstone in many ...

ELSEVIER FRANCE-EDITIONS SCIENTIFIQUES MEDICALES ELSEVIER2019