Publication

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Publications associées (134)

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

On two coloring problems in mixed graphs

Dominique de Werra, Bernard Ries

We are interested in coloring the vertices of a mixed graph, i.e., a graph containing edges and arcs. We consider two different coloring problems: in the first one we want adjacent vertices to have different colors and the tail of an arc to get a color str ...

2008

Parity-regular Steinhaus graphs

Maxime Augier

Steinhaus graphs on n vertices are certain simple graphs in bijective correspondence with binary {0,1}-sequences of length n-1. A conjecture of Dymacek in 1979 states that the only nontrivial regular Steinhaus graphs are those corresponding to the periodic ...

American Mathematical Society2008

Visual Debugging of MPI Applications

Roger Hersch, Ali Al-Shabibi

We present the design and implementation of a debugging tool that displays a message-passing graph of the execution of an MPI application. Parts of the graph can be hidden or highlighted based on the stack trace, calling process or communicator of MPI call ...

Springer2008

Automated Delineation of Dendritic Networks in Noisy Image Stacks

Pascal Fua, François Fleuret, Germán González Serrano

We present a novel approach to 3D delineation of dendritic networks in noisy image stacks. We achieve a level of automation beyond that of state-of-the-art systems, which model dendrites as continuous tubular structures and postulate simple appearance mode ...

Springer-Verlag2008

Variations of coloring problems related to scheduling and discrete tomography

Bernard Ries

The graph coloring problem is one of the most famous problems in graph theory and has a large range of applications. It consists in coloring the vertices of an undirected graph with a given number of colors such that two adjacent vertices get different col ...

EPFL2007

Bicolored matchings in some classes of graphs

Dominique de Werra, Bernard Ries

We consider the problem of finding in a graph a set

R

of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with

n

nodes on each side, we give sufficient conditions f ...

2007

Coloring some classes of mixed graphs

Bernard Ries

We consider the coloring problem for mixed graphs, that is, for graphs containing edges and arcs. A mixed coloring

c

is a coloring such that for every edge

[x_{i},x_{j}]

c(x_{i})\neq c(x_{j})

and for every arc

(x_{p},x_{q})

, $c(x_{p})

2007

Recognition of generalized network matrices

Antoine Musitelli

In this thesis, we deal with binet matrices, an extension of network matrices. The main result of this thesis is the following. A rational matrix A of size n×m can be tested for being binet in time O(n6m). If A is binet, our algorithm outputs a nonsingular ...

EPFL2007

Online Coloring of Comparability Graphs: some results

Benjamin Leroy-Beaulieu

We study online partitioning of posets from a graph theoretical point of view, which is coloring and cocoloring in comparability graphs. For the coloring problem, we analyse the First-Fit algorithm and show a ratio of

O(\sqrt{n})

; furthermore, we devise ...

2007

(k,lambda)-colorings and universal graphs

Ivo Blöchliger, Daniela Bronner

We consider vertex k-colorings of an arbitrary simple, connected, and undirected graph G=(V,E) such that, for every vertex v, at most lambda different colors occur in the closed neighborhood of v. These colorings are called (k,lambda)-colorings. If a graph ...

2006