Concept

Arbre couvrant de poids minimal

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

Metapopulation capacity of evolving fluvial landscapes

Andrea Rinaldo, Enrico Bertuzzo

The form of fluvial landscapes is known to attain stationary network configurations that settle in dynamically accessible minima of total energy dissipation by landscape-forming discharges. Recent studies have highlighted the role of the dendritic structur ...

American Geophysical Union2015

Controls on the diurnal streamflow cycles in two subbasins of an alpine headwater catchment

Marc Parlange, Steven Vincent Weijs, Marc Calaf Bracons, Holly Jayne Oldroyd, Raphaël Mutzner

In high-altitude alpine catchments, diurnal streamflow cycles are typically dominated by snowmelt or ice melt. Evapotranspiration-induced diurnal streamflow cycles are less observed in these catchments but might happen simultaneously. During a field campai ...

American Geophysical Union2015

Right-Protected Data Publishing with Provable Distance-Based Mining

Michail Vlachos, Nikolaos Freris

Protection of one's intellectual property is a topic with important technological and legal facets. We provide mechanisms for establishing the ownership of a dataset consisting of multiple objects. The algorithms also preserve important properties of the d ...

Ieee Computer Soc2014

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~

3

. Then, we draw a connection to Goem ...

EPFL2014

Population Sensing Using Mobile Devices

Farid Movahedi Naini

In our daily lives, our mobile phones sense our movements and interactions via a rich set of embedded sensors such as a GPS, Bluetooth, accelerometers, and microphones. This enables us to use mobile phones as agents for collecting spatio-temporal data. The ...

EPFL2014

Evolution and selection of river networks: Statics, dynamics, and complexity

Andrea Rinaldo, Amos Maritan

Moving from the exact result that drainage network configurations minimizing total energy dissipation are stationary solutions of the general equation describing landscape evolution, we review the static properties and the dynamic origins of the scale-inva ...

Natl Acad Sciences2014

Reversible Sesqui-Pushout Rewriting, Graph Transformation

Sandro Stucki

The paper proposes a variant of sesqui-pushout rewriting (SqPO) that allows one to develop the theory of nested application conditions (NACs) for arbitrary rule spans; this is a considerable generalisation compared with existing results for NACs, which onl ...

Springer2014

Steiner Tree Approximation via Iterative Randomized Rounding

Thomas Rothvoss, Laura Sanità

The Steiner tree problem is one of the most fundamental 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 this problem w ...

Assoc Computing Machinery2013

HELEN: A Public-Key Cryptosystem Based on the LPN and the Decisional Minimal Distance Problems

Serge Vaudenay, Alexandre Raphaël Duc

We propose HELEN, a code-based public-key cryptosystem whose security is based on the hardness of the Learning from Parity with Noise problem (LPN) and the decisional minimum distance problem. We show that the resulting cryptosystem achieves indistinguisha ...

Springer2013

Monochromatic empty triangles in two-colored point sets

János Pach

Improving a result of Aichholzer et al., we show that there exists a constant c > 0 satisfying the following condition. Any two-colored set of n points in general position in the plane has at least cn(4/3) triples of the same color such that the triangles ...

Elsevier Science Bv2013

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

3

. Then, we draw a connection to Goem ...

EPFL2014