Publications associées à Bounded expansion

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

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

Testing Graph Clusterability: Algorithms and Lower Bounds

Mikhail Kapralov, Aidasadat Mousavifar, Ashish Hari Chiplunkar

We consider the problem of testing graph cluster structure: given access to a graph G = (V, E), can we quickly determine whether the graph can be partitioned into a few clusters with good inner conductance, or is far from any such graph? This is a generali ...

IEEE COMPUTER SOC2018

Lower Bounds on Active Learning for Graphical Model Selection

Volkan Cevher, Jonathan Mark Scarlett

We consider the problem of estimating the underlying graph associated with a Markov random field, with the added twist that the decoding algorithm can iteratively choose which subsets of nodes to sample based on the previous samples, resulting in an active ...

2017

On the Zarankiewicz problem for intersection hypergraphs

János Pach

Let d and t be fixed positive integers, and let denote the complete d-partite hypergraph with t vertices in each of its parts, whose hyperedges are the d-tuples of the vertex set with precisely one element from each part. According to a fundamental theorem ...

Academic Press Inc Elsevier Science2016

Exponential extinction time of the contact process on finite graphs

Thomas Mountford, Daniel Rodrigues Valesin, Jean-Christophe Mourrat

We study the extinction time tau of the contact process started with full occupancy on finite trees of bounded degree. We show that, if the infection rate is larger than the critical rate for the contact process on Z, then, uniformly over all trees of degr ...

Elsevier Science Bv2016

Drawing Planar Graphs Of Bounded Degree With Few Slopes

János Pach, Balázs Keszegh, Doemoetoer Palvoelgyi

We settle a problem of Dujmovic, Eppstein, Suderman, and Wood by showing that there exists a function f with the property that every planar graph G with maximum degree d admits a drawing with noncrossing straight-line edges, using at most f(d) different sl ...

SIAM Publications2013

Design and Optimization of Orthogonally Intersecting Planar Surfaces

Mark Pauly, Yuliy Gennadievich Schwartzburg

We present a method for the design of 3D constructions from planar pieces that can be cut easily and cheaply with laser cutters and similar Computer Numerical Control (CNC) machines. By cutting tight slits in intersecting pieces, they can be slid into each ...

Springer Berlin Heidelberg2012

Drawing planar graphs of bounded degree with few slopes

János Pach, Balázs Keszegh, Doemoetoer Palvoelgyi

We settle a problem of Dujmovic, Eppstein, Suderman, and Wood by showing that there exists a function f with the property that every planar graph G with maximum degree d admits a drawing with noncrossing straight-line edges, using at most f(d) different sl ...

Springer-Verlag2011

Decomposition of Geometric Set Systems and Graphs

Doemoetoer Palvoelgyi

We study two decomposition problems in combinatorial geometry. The first part of the thesis deals with the decomposition of multiple coverings of the plane. We say that a planar set is cover-decomposable if there is a constant m such that any m-fold coveri ...

EPFL2010

A simple test to check the optimality of a sparse signal approximation

Pierre Vandergheynst, Rémi Gribonval

Approximating a signal or an image with a sparse linear expansion from an overcomplete dictionary of atoms is an extremely useful tool to solve many signal processing problems. Finding the sparsest approximation of a signal from an arbitrary dictionary is ...

2006