Publication

Polar cographs

Publications associées (159)

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

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

Wavelets on Graphs via Spectral Graph Theory

Pierre Vandergheynst, Rémi Gribonval

We propose a novel method for constructing wavelet transforms of functions defined on the vertices of an arbitrary finite graph. We define a notion of scaling using the graph analogue of the Fourier domain, namely the space of eigenfunctions forming the sp ...

2008

The stable set polytope of quasi-line graphs

Friedrich Eisenbrand, Gautier Stauffer

It is a long standing open problem to find an explicit description of the stable set polytope of claw-free graphs. Yet more than 20 years after the discovery of a polynomial algorithm for the maximum stable set problem for claw-free graphs, there is even n ...

2008

On a graph coloring problem arising from discrete tomography

Dominique de Werra, Bernard Ries

An extension of the basic image reconstruction problem in discrete tomography is considered: given a graph

G=(V,E)

and a family

\mathcal{P}

of chains

P_i

together with vectors

h(P_i)=(h_{i}^{1},...,h_{i}^{k})

, one wants to find a partition $V^{1},. ...

2008

Finding Hamiltonian circuits in quasi-adjoint graphs

Dominique de Werra, Benjamin Leroy-Beaulieu

This paper is motivated by a method used for DNA sequencing by hybridization presented in [Jacek Blazewicz, Marta Kasprzak, Computational complexity of isothernnic DNA sequencing by hybridization, Discrete Appl. Math. 154 (5) (2006) 718-7291. This paper pr ...

2008

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

Dynamical dimer correlations at bipartite and non-bipartite Rokhsar-Kivelson points

We determine the dynamical dimer correlation functions of quantum dimer models at the Rokhsar-Kivelson point on the bipartite square and cubic lattices and the non-bipartite triangular lattice. On the basis of an algorithmic idea by Henley, we simulate a s ...

2008

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

Generalized vertex coloring problems using split graphs

Tinaz Ekim

Graph theory experienced a remarkable increase of interest among the scientific community during the last decades. The vertex coloring problem (Min Coloring) deserves a particular attention rince it has been able to capture a wide variety of applications. ...

EPFL2006