Concept

Vertex cover

Related publications (121)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Inference of Mobility Patterns via Spectral Graph Wavelets

Pascal Frossard, Pierre Vandergheynst, Xiaowen Dong

Modern data processing tasks frequently involve structured data, for example signals defined on the vertex set of a weighted graph. In this paper, we address the problem of inference of mobility patterns from data defined on geographical graphs based on sp ...

2013

Application of vertex and mass constraints in track-based alignment

Olivier Schneider, Christophe Salzmann, Matthew Needham, Maurizio Martinelli, Frédéric Guillaume Dupertuis, Vincent Fave, Géraldine Conti, Louis Nicolas, Gerhard Raven

The software alignment of planar tracking detectors using samples of charged particle trajectories may lead to global detector distortions that affect vertex and momentum resolution. We present an alignment procedure that constrains such distortions by mak ...

Elsevier Science Bv2013

The number of distinct distances from a vertex of a convex polygon

János Pach, Rom Pinchasi, Gabriel Nivasch

Erd\H{o}s conjectured in 1946 that every n-point set P in convex position in the plane contains a point that determines at least floor(n/2) distinct distances to the other points of P. The best known lower bound due to Dumitrescu (2006) is 13n/36 - O(1). I ...

2013

Message-Passing Algorithms for Quadratic Minimization

Nicholas Ruozzi

Gaussian belief propagation (GaBP) is an iterative algorithm for computing the mean (and variances) of a multivariate Gaussian distribution, or equivalently, the minimum of a multivariate positive definite quadratic function. Sufficient conditions, such as ...

Microtome Publ2013

The Range of a Random Walk on a Comb

János Pach, Gábor Tardos

The graph obtained from the integer grid Z x Z by the removal of all horizontal edges that do not belong to the x-axis is called a comb. In a random walk on a graph, whenever a walker is at a vertex v, in the next step it will visit one of the neighbors of ...

Electronic Journal Of Combinatorics2013

To Convexify or Not? Regression with Clustering Penalties on Graphs

Volkan Cevher, Luca Baldassarre, Marwa El Halabi

We consider minimization problems that are compositions of convex functions of a vector

\x \in\reals^N

with submodular set functions of its support (i.e., indices of the non-zero coefficients of

\x

). Such problems are in general difficult for large

N

...

IEEE2013

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

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

String graphs and incomparability graphs

János Pach

Given a collection C of curves in the plane, its string graph is defined as the graph with vertex set C, in which two curves in C are adjacent if and only if they intersect. Given a partially ordered set (P,