Publication
The flip-graph of the 4-dimensional cube is connected
Publications associées (32)
Modeling Network Populations via Graph Distances
This article introduces a new class of models for multiple networks. The core idea is to parameterize a distribution on labeled graphs in terms of a Frechet mean graph (which depends on a user-specified choice of metric or graph distance) and a parameter t ...
AMER STATISTICAL ASSOC2020Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
Mikhail Kapralov, Slobodan Mitrovic, Ashkan Norouzi Fard, Jakab Tardos
Given a source of iid samples of edges of an input graph G with n vertices and m edges, how many samples does one need to compute a constant factor approximation to the maximum matching size in G? Moreover, is it possible to obtain such an estimate in a sm ...
ASSOC COMPUTING MACHINERY2020Ordered Graphs And Large Bi-Cliques In Intersection Graphs Of Curves
An ordered graph G(
COMENIUS UNIV2019Ordered graphs and large bi-cliques in intersection graphs of curves
An ordered graph G(
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD2019No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon
Ola Nils Anders Svensson, Abbas Bazzi
The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...
INFORMS2019New Graph Algorithms via Polyhedral Techniques
In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...
EPFL2019A note on discrete lattice-periodic sets with an application to Archimedean tilings
Cao and Yuan obtained a Blichfeldt-type result for the vertex set of the edge-to-edge tiling of the plane by regular hexagons. Observing that the vertex set of every Archimedean tiling is the union of translates of a fixed lattice, we take a more general v ...
SPRINGER HEIDELBERG2019On the Turan number of ordered forests
Gábor Tardos, Istvan Tomon, Dániel József Korándi
An ordered graph H is a simple graph with a linear order on its vertex set. The corresponding Turan problem, first studied by Pach and Tardos, asks for the maximum number ex(
ACADEMIC PRESS INC ELSEVIER SCIENCE2019When Stuck, Flip a Coin
Many modern services need to routinely perform tasks on a large scale. This prompts us to consider the following question:
How can we design efficient algorithms for large-scale computation?
In this thesis, we focus on devising a general strategy to addr ...
EPFL2018Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
Slobodan Mitrovic, Mohsen Ghaffari
We present O(log log n)-round algorithms in the Massively Parallel Computation (MPC) model, with a(n) memory per machine, that compute a maximal independent set, a 1 + epsilon approximation of maximum matching, and a 2 + epsilon approximation of minimum ve ...
ASSOC COMPUTING MACHINERY2018