Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Treewidth

Related publications (11)

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

Akash Kumar

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...

IEEE COMPUTER SOC2022

Exponential Convergence for the Fredrickson-Andersen One-Spin Facilitated Model

Thomas Mountford

We prove exponential convergence to equilibrium for the Fredrickson-Andersen one-spin facilitated model on bounded degree graphs satisfying a subexponential, but larger than polynomial, growth condition. This was a classical conjecture related to non-attra ...

SPRINGER/PLENUM PUBLISHERS2019

Computation in Multicast Networks: Function Alignment and Converse Theorems

Michael Christoph Gastpar, Naveen Goela

The classical problem in a network coding theory considers communication over multicast networks. Multiple transmitters send independent messages to multiple receivers that decode the same set of messages. In this paper, computation over multicast networks ...

Institute of Electrical and Electronics Engineers2016

Sparse Group Covers and Greedy Tree Approximations

Volkan Cevher, Luca Baldassarre

We consider the problem of finding a K-sparse approximation of a signal, such that the support of the approximation is the union of sets from a given collection, a.k.a. group structure. This problem subsumes the one of finding K-sparse tree approximations. ...

2015

Breaking Anchored Droplets in a Microfluidic Hele-Shaw Cell

François Gallaire, Pierre-Thomas Paul Brun

We study microfluidic self-digitization in Hele-Shaw cells using pancake droplets anchored to surface-tension traps. We show that above a critical flow rate, large anchored droplets break up to form two daughter droplets, one of which remains in the anchor ...

American Physical Society (APS)2015

Outerplanar graph drawings with few slopes

Bartosz Maria Walczak

We consider straight-line outerplanar drawings of outerplanar graphs in which a small number of distinct edge slopes are used, that is, the segments representing edges are parallel to a small number of directions. We prove that Delta - 1 edge slopes suffic ...

Elsevier Science Bv2014

Decomposition and tractability in qualitative spatial and temporal reasoning

Jingshi Li

Constraint networks in qualitative spatial and temporal reasoning (QSTR) typically feature variables defined on infinite domains. Mainstream algorithms for deciding network consistency are based on searching for network refinements whose consistency is kno ...

Elsevier2013

Admittance Matrix of a Trapezoidal Piezoelectric Heterogeneous Bimorph

Paul Muralt

Bimorph structures are a standard method for transforming the high force of piezoelectric materials into a large deflection. In micro electromechanical systems (MEMS) applications, it is preferable to use structures consisting of a passive substrate (usual ...

Ieee-Inst Electrical Electronics Engineers Inc2012

Optimization of the wire grid size for differential routing: Analysis and impact on the power-delay-area tradeoff

Yusuf Leblebici

In this paper, the impact of the wire grid size on the power-delay-area trade off of VLSI digital circuits with differential routing is analyzed. To this aim, the differential MOS current-mode logic (MCML) is adopted as reference logic style, and a complet ...

Elsevier2010

Subtree-based bounds and simulation-based estimations for the partition function

Mehdi Molkaraie

Many different algorithms developed in statistical physics, coding theory, signal processing, and artificial intelligence can be expressed by graphical models and solved (either exactly or approximately) with iterative message-passing algorithms on the mod ...

EPFL2007

Tree-Based Pursuit: Algorithm and Properties

Pascal Frossard, Pierre Vandergheynst, Philippe Jost

This paper proposes a tree-based pursuit algorithm that efficiently trades off complexity and approximation performance for overcomplete signal expansions. Finding the sparsest representation of a signal using a redundant dictionary is, in general, a NP-Ha ...

2006

Related publications (11)