Publication

Exceptional graphs for the random walk

Publications associées (32)

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

Lower bounds on the obstacle number of graphs

János Pach, Doemoetoer Palvoelgyi, Padmini Mukkamala

Given a graph G, an obstacle representation of G is a set of points in the plane representing the vertices of G, together with a set of connected obstacles such that two vertices of G are joined by an edge if and only if the corresponding points can be con ...

2012

Direct observation of the full transition from ballistic to diffusive Brownian motion in a liquid

Sylvia Jeney, Branimir Lukic

At timescales once deemed immeasurably small by Einstein, the random movement of Brownian particles in a liquid is expected to be replaced by ballistic motion. So far, an experimental verification of this prediction has been out of reach due to a lack of i ...

2011

An Improved LP-based Approximation for Steiner Tree

Thomas Rothvoss, Laura Sanità

The Steiner tree problem is one of the most fundamental

\mathbf{NP}

-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for thi ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2010

Simulation by circular embedding method of max-stable random fields

Nathalie Pellet

Theory of random fields or random processes is presented with an emphasis on the possible choices of correlation functions. Then two methods for generating Gaussian random fields in Rd are presented. The first method is a direct one but does not work for a ...

2009

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

Glass patterns in the superposition of random line gratings

Isaac Amidror

Moire effects ('Glass patterns') that occur in the superposition of correlated random layers have long been studied. However, only little is known of Glass patterns which occur in the 1D random case: namely, when the superposed layers consist of random lin ...

IOP Publishing2003

Bethe approximation for self-interacting lattice trees

Paolo De Los Rios

In this paper we develop a Bethe approximation, based on the cluster variation method, which is apt to study lattice models of branched polymers. We show that the method is extremely accurate in cases where exact results are known as, for instance, in the ...

EDP Sciences2001

Average-case analysis of dynamic graph algorithms

Monika Henzinger

We present a model for edge updates with restricted randomness in dynamic graph algorithms and a general technique for analyzing the expected running time of an update operation. This model is able to capture the average case in many applications, since (1 ...

1998

We introduce a new set of probabilistic analysis tools based on the analysis of And-Or trees with random inputs. These tools provide a unifying, intuitive, and powerful framework for carrying out the analysis of several previously studied random processes ...