Publication

Degree-constrained edge partitioning in graphs arising from discrete tomography

Publications associées (283)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

The Erdos-Hajnal conjecture for rainbow triangles

János Pach

We prove that every 3-coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a set of order ohm(n(1/3) log(2) n) which uses at most two colors, and this bound is tight up to a constant factor. This verifies a conjectu ...

Academic Press Inc Elsevier Science2015

Downsampling of Signals on Graphs Via Maximum Spanning Trees

Quy Ha Nguyen, Minh Do

Downsampling of signals living on a general weighted graph is not as trivial as of regular signals where we can simply keep every other samples. In this paper we propose a simple, yet effective downsampling scheme in which the underlying graph is approxima ...

Ieee-Inst Electrical Electronics Engineers Inc2015

Modeling and Controlling epidemics : a graph perspective

Philippe Sakari Rossinelli

The social and economical impact a virus has in a population is not negligible. For this reason, gaining a theoretical understanding of the behavior of a virus is of prime importance. This project is going to be divided in several parts. First, we will dis ...

2015

Spectrum-Adapted Tight Graph Wavelet and Vertex-Frequency Frames

Pierre Vandergheynst, David Shuman

We consider the problem of designing spectral graph filters for the construction of dictionaries of atoms that can be used to efficiently represent signals residing on weighted graphs. While the filters used in previous spectral graph wavelet constructions ...

Institute of Electrical and Electronics Engineers2015

Chaos: Scale-out Graph Processing from Secondary Storage

Willy Zwaenepoel, Laurent Bindschaedler, Amitabha Roy, Jasmina Malicevic

Chaos scales graph processing from secondary storage to multiple machines in a cluster. Earlier systems that process graphs from secondary storage are restricted to a single ma- chine, and therefore limited by the bandwidth and capacity of the storage syst ...

2015

Free Edge Lengths in Plane Graphs

Radoslav Fulek, Filip Moric

We study the impact of metric constraints on the realizability of planar graphs. Let G be a subgraph of a planar graph H (where H is the "host" of G). The graph G is free in H if for every choice of positive lengths for the edges of G, the host H has a pla ...

Springer2015

Multi-Graph Learning of Spectral Graph Dictionaries

Pascal Frossard

We study the problem of learning constitutive features for the effective representation of graph signals, which can be considered as observations collected on different graph topologies. We propose to learn graph atoms and build graph dictionaries that pro ...

2015

Moment Semantics for Reversible Rule-Based Systems

Sandro Stucki

We develop a notion of stochastic rewriting over marked graphs – i.e. directed multigraphs with degree constraints. The approach is based on double-pushout (DPO) graph rewriting. Marked graphs are expressive enough to internalize the ‘no-dangling-edge’ con ...

Springer International Publishing2015

Robust Principal Component Analysis on Graphs

Pierre Vandergheynst, Michael Bronstein, Xavier Bresson, Nauman Shahid, Vasilis Kalofolias

Principal Component Analysis (PCA) is the most widely used tool for linear dimensionality reduction and clustering. Still it is highly sensitive to outliers and does not scale well with respect to the number of data samples. Robust PCA solves the first iss ...

2015

Orchestration Graphs

Pierre Dillenbourg

By modeling pedagogical scenarios as directed geometrical graphs and proposing an associated modeling language, this book describes how rich learning activities, often designed for small classes, can be scaled up for use with thousands of participants. Wit ...

EPFL Press2015