Publication

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

Publications associées (211)

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

d-Transversals of stable sets and vertex covers in weighted bipartite graphs

Dominique de Werra, Bernard Ries

Let G=(V,E)G=(V,E) be a graph in which every vertex v∈Vv∈V has a weight w(v)⩾0w(v)⩾0 and a cost c(v)⩾0c(v)⩾0. Let SGSG be the family of all maximum-weight stable sets in G . For any integer d⩾0d⩾0, a minimum d-transversal in the graph G with respect to SGS ...

2012

Finite graphs and amenability

Gábor Elek

Hyperfiniteness or amenability of measurable equivalence relations and group actions has been studied for almost fifty years. Recently, unexpected applications of hyperfiniteness were found in computer science in the context of testability of graph propert ...

Academic Press Inc Elsevier Science2012

Multi-Graph Sampling Of Online Communities Via Mean Hitting Time

We derive a framework for sampling online communities based on the mean hitting time of its members, considering that there are multiple graphs associated with the same vertex set V representing the social network. First, we formulate random walk models on ...

Ieee2012

Robust Non-Rigid Registration of 2D and 3D Graphs

Pascal Fua, Jan Kybic, Przemyslaw Rafal Glowacki

We present a new approach to matching graphs embedded in R2 or R3. Unlike earlier methods, our approach does not rely on the similarity of local appearance features, does not require an initial alignment, can handle partial matches, and can cope with non-l ...

2012

Clustering with Multi-Layer Graphs: A Spectral Perspective

Pascal Frossard, Pierre Vandergheynst, Xiaowen Dong

Observational data usually comes with a multimodal nature, which means that it can be naturally represented by a multi-layer graph whose layers share the same set of vertices (users) with different edges (pairwise relationships). In this paper, we address ...

Institute of Electrical and Electronics Engineers2012

Simplex solids in SU(N) Heisenberg models on the kagome and checkerboard lattices

Frédéric Mila, Karlo Penc

We present a numerical study of the SU(N) Heisenberg model with the fundamental representation at each site for the kagome lattice (for N = 3) and the checkerboard lattice (for N = 4), which are the line graphs of the honeycomb and square lattices and thus ...

2012

Coloring K-k-free intersection graphs of geometric objects in the plane

János Pach

The intersection graph of a collection C of sets is the graph on the vertex set C, in which C-1 . C-2 is an element of C are joined by an edge if and only if C-1 boolean AND C-2 not equal empty set. Erdos conjectured that the chromatic number of triangle-f ...

2012

Graph Drawing

Radoslav Fulek, Fabrizio Frati

In this paper we study the page number of upward planar directed acyclic graphs. We prove that the page number of any upward planar directed acyclic graph G is a function of the page number of a four-connected subgraph of G; further, we provide an upper bo ...

Springer Berlin Heidelberg2012

Efficient graph planarization in sensor networks and local routing algorithm

Florian Huc

In this paper, we propose an efficient planarization algorithm and a routing algorithm dedicated to Unit Disk Graphs whose nodes are localized using the Virtual Raw Anchor Coordinate system (VRAC). Our first algorithm computes a planar 2-spanner under ligh ...

Ieee2012

Tangled Thrackles

János Pach

A tangle is a graph drawn in the plane so that any pair of edges have precisely one point in common, and this point is either an endpoint or a point of tangency. If we allow a third option: the common point may be a proper crossing between the two edges, t ...

Springer Berlin Heidelberg2012