Publication
Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
Publications associées (40)
A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing
In this paper, we prove several extremal results for geometrically defined hypergraphs. In particular, we establish an improved lower bound, single exponentially decreasing in k, on the best constant delta > 0 such that the vertex classes P-1,...,P-k of ev ...
Society for Industrial and Applied Mathematics2016Partial 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 and respectively. We consider the ...
Ieee2016A Precise Threshold For Quasi-Ramsey Numbers
We consider the variation of Ramsey numbers introduced by Erdos and Pach [J. Graph Theory, 7 (1983), pp. 137-147], where instead of seeking complete or independent sets we only seek a t-homogeneous set, a vertex subset that induces a subgraph of minimum de ...
Siam Publications2015Homometric sets in trees
Radoslav Fulek, Slobodan Mitrovic
Let G = (V, E) denote a simple graph with vertex set V and edge set E. The profile of a vertex set V' subset of V denotes the multiset of pairwise distances between the vertices of V'. Two disjoint subsets of V are homometric if their profiles are the same ...
Academic Press Ltd- Elsevier Science Ltd2014Exponentiality of the exchange algorithm for finding another room-partitioning
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 Bv2014On the Performance of Percolation Graph Matching
Matthias Grossglauser, Lyudmila Yartseva
Graph matching is a generalization of the classic graph isomorphism problem. By using only their structures a graph-matching algorithm finds a map between the vertex sets of two similar graphs. This has applications in the de-anonymization of social and in ...
ACM2013Large simplices determined by finite point sets
Given a set P of n points in ℝd, let d1 > d2 >...denote all distinct inter-point distances generated by point pairs in P. It was shown by Schur, Martini, Perles, and Kupitz that there is at most oned-dimensional regular simplex of edge length d1 whos ...
Springer-Verlag2013Optimizing 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 ...
2013The flip-graph of the 4-dimensional cube is connected
Flip-graph connectedness is established here for the vertex set of the 4-dimensional cube. It is found as a consequence, that this vertex set admits 92487256 triangulations, partitioned into 247451 symmetry classes. ...
Springer-Verlag2013d-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