Concept

Graphe dual

Publications associées (182)

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

Diameter Bounds for Planar Graphs

Radoslav Fulek, Filip Moric, David Pritchard

The inverse degree of a graph is the sum of the reciprocals of the degrees of its vertices. We prove that in any connected planar graph, the diameter is at most 5/2 times the inverse degree, and that this ratio is tight. To develop a crucial surgery method ...

Elsevier2011

Lower Bounds on the Area Requirements of Series-Parallel Graphs

Fabrizio Frati

We show that there exist series-parallel graphs requiring Omega(n2(root log n)) area in any straight-line or poly-line grid drawing. Such a result is achieved in two steps. First, we show that, in any straight-line or poly-line drawing of K-2,K-n, one side ...

2011

A lower bound for algebraic connectivity based on the connection-graph-stability method

Martin Hasler, Ali Ajdari Rad, Mahdi Jalili

This paper introduces the connection-graph-stability method and uses it to establish a new lower bound on the algebraic connectivity of graphs (the second smallest eigenvalue of the Laplacian matrix of the graph) that is sharper than the previously publish ...

Elsevier2011

Primal-dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs

Carsten Moldenhauer

NODE-WEIGHTED STEINER FOREST is the following problem: Given an undirected graph, a set of pairs of terminal vertices, a weight function on the vertices, find a minimum weight set of vertices that includes and connects each pair of terminals. We consider t ...

Academic Press Inc Elsevier Science2011

Methods for Clustering Multi-Layer Graphs in Mobile Networks

Pascal Frossard, Pierre Vandergheynst, Xiaowen Dong

Clustering on graphs has been studied extensively for years due to its numerous applications. However, in contrast to the classic problems, clustering in mobile and online social networks brings new challenges. In these scenarios, it is common that observa ...

2011

Functional Webs for Freeform Architecture

Bailin Deng

Rationalization and construction-aware design dominate the issue of realizability of freeform architecture. The former means the decomposition of an intended shape into parts which are sufficiently simple and efficient to manufacture; the latter refers to ...

Wiley-Blackwell2011

Omnidirectional Object Duplicate Detection

Touradj Ebrahimi, Lutz Goldmann, Ivan Ivanov, Péter Vajda

In this paper, we extend a graph-based approach for omnidirectional object duplicate detection in still images. Objects are detected from several points of view with different distances. The goal of this work is to determine how many training images have t ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2011

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 weighted graph. Our approach is based on defining scaling using the the graph analogue of the Fourier domain, namely the spectral deco ...

Elsevier2011

Electromagnetic Modelling of Planar Circuits Embedded in Laterally Shielded Multilayered Media

Laleh Golestanirad

Multilayered media with printed circuits embedded between their dielectric layers are one of the most successful technologies for manufacturing planar structures with a very promising performance-to-price ratio. These planar structures include many differe ...

EPFL2011

A scenario approach for estimating the suboptimality of linear decision rules in two-stage robust optimization

Daniel Kuhn

Robust dynamic optimization problems involving adaptive decisions are computationally intractable in general. Tractable upper bounding approximations can be obtained by requiring the adaptive decisions to be representable as linear decision rules (LDRs). I ...

IEEE2011