Publications related to Minimum d-blockers and d-transversals in graphs

On vertices and facets of combinatorial 2-level polytopes

Yuri Faenza, Manuel Francesco Aprile, Alfonso Bolívar Cevallos Manzano

2-level polytopes naturally appear in several areas of mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and statistics. We investigate upper bounds on the product of the number of facets and the number ...

Springer2016

Partial Recovery Bounds for the Sparse Stochastic Block Model

Volkan Cevher, Jonathan Mark Scarlett

In this paper, we study the information-theoretic limits of community detection in the symmetric two-community stochastic block model, with intra-community and inter-community edge probabilities

\frac{a}{n}

and

\frac{b}{n}

respectively. We consider the ...

Ieee2016

Sampling Curves with Finite Rate of Innovation

Thierry Blu, Hanjie Pan, Pier Luigi Dragotti

In this paper, we extend the theory of sampling signals with finite rate of innovation (FRI) to a specific class of two-dimensional curves, which are defined implicitly as the zeros of a mask function. Here the mask function has a parametric representation ...

Institute of Electrical and Electronics Engineers2014

Exponentiality of the exchange algorithm for finding another room-partitioning

Laura Sanità

Let T be a triangulated surface given by the list of vertex-triples of its triangles, called rooms. A room-partitioning for T is a subset R of the rooms such that each vertex of T is in exactly one room in R. Given a room-partitioning R for T, the exchange ...

Elsevier Science Bv2014

Association Generation in Synthetic Population for Transportation Applications: Graph-Theoretic Solution

Michel Bierlaire, Bilal Farooq, Dimitrios Efthymiou, Paul Richard Anderson

The generation of synthetic populations through simulation methods is an important research topic and has a key application in agent-based modeling of transport and land use. The next step in this research area is the generation of complete synthetic house ...

Natl Acad Sciences2014

A Bayesian Method for Matching Two Similar Graphs without Seeds

Matthias Grossglauser, Pedram Pedarsani

Approximate graph matching (AGM) refers to the problem of mapping the vertices of two structurally similar graphs, which has applications in social networks, computer vision, chemistry, and biology. Given its computational cost, AGM has mostly been limited ...

2013

Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

Aleksander Madry

We present an O(m^10/7) = O(m^1.43)-time algorithm for the maximum s-t flow and the minimum s-t cut problems in directed graphs with unit capacities. This is the first improvement over the sparse-graph case of the long-standing O(m min{m^1/2, n^2/3}) runni ...

IEEE2013

Optimizing Mix-zone Coverage in Pervasive Wireless Networks

Jean-Pierre Hubaux, Murtuza Jadliwala, Igor Bilogrevic

Location privacy is a major concern in pervasive networks where static device identifiers enable malicious eavesdroppers to continuously track users and their movements. In order to prevent such identifier-based tracking, devices could coordinate regular i ...

2013

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

Lower bounds on the obstacle number of graphs

János Pach, Doemoetoer Palvoelgyi, Padmini Mukkamala

Given a graph G, an obstacle representation of G is a set of points in the plane representing the vertices of G, together with a set of connected obstacles such that two vertices of G are joined by an edge if and only if the corresponding points can be con ...

2012

Minimum d-blockers and d-transversals in graphs

Graph Chatbot

Chat with Graph Search

On vertices and facets of combinatorial 2-level polytopes

Partial Recovery Bounds for the Sparse Stochastic Block Model

Sampling Curves with Finite Rate of Innovation

Exponentiality of the exchange algorithm for finding another room-partitioning

Association Generation in Synthetic Population for Transportation Applications: Graph-Theoretic Solution

A Bayesian Method for Matching Two Similar Graphs without Seeds

Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

Optimizing Mix-zone Coverage in Pervasive Wireless Networks

d-Transversals of stable sets and vertex covers in weighted bipartite graphs

Lower bounds on the obstacle number of graphs

Optimizing Mix-zone Coverage in Pervasive Wireless Networks

Lower bounds on the obstacle number of graphs

Sampling Curves with Finite Rate of Innovation

Exponentiality of the exchange algorithm for finding another room-partitioning

On vertices and facets of combinatorial 2-level polytopes

A Bayesian Method for Matching Two Similar Graphs without Seeds

Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

d-Transversals of stable sets and vertex covers in weighted bipartite graphs

Association Generation in Synthetic Population for Transportation Applications: Graph-Theoretic Solution

Partial Recovery Bounds for the Sparse Stochastic Block Model