We develop an algorithm to solve the bottleneck assignment problem (BAP) that is amenable to having computation distributed over a network of agents. This consists of exploring how each component of the algorithm can be distributed, with a focus on one com ...
Building replacement (BR) – i.e., the demolition of existing structures and subsequent construction of new buildings on the same site – is often understood as a necessary urban planning strategy despite significant environmental implications regarding soli ...
We study the performance of Markov chains for the q-state ferromagnetic Potts model on random regular graphs. While the cases of the grid and the complete graph are by now well-understood, the case of random regular graphs has resisted a detailed analysis ...
We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks-Seymour problem in graph theory (posed in 1991), which ...
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 ...
The exploration of one-factorizations of complete graphs is the foundation of some classical sports scheduling problems. One has to traverse the landscape of such one-factorizations by moving from one of those to a so-called neighbor one-factorization. Thi ...
Gossip protocols (also called rumor spreading or epidemic protocols) are widely used to disseminate information in massive peer-to-peer networks. These protocols are often claimed to guarantee privacy because of the uncertainty they introduce on the node t ...
Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs. An important observation for such results is that if G is an n-vertex graph that is ...
An abstract topological graph (briefly an AT-graph) is a pair A = (G, X) where G = (V, E) is a graph and X. E2 is a set of pairs of its edges. The AT-graph A is simply realizable if G can be drawn in the plane so that each pair of edges from X crosses exac ...
A clique covering of a graph G is a set of cliques of G such that any edge of G is contained in one of these cliques, and the weight of a clique covering is the sum of the sizes of the cliques in it. The sigma clique cover number scc(G) of a graph G, is de ...
