 |
My Publications |
Publications on Journals
3) Dellamonica and Yoshiharu Kohayakawa, An algorithmic Friedman-Pippenger theorem on tree embeddings, The Electronic Journal of Combinatorics, vol 15(1), R127.
Abstract: An $(n, d)$-expander is a graph $G = (V , E)$
such that for every $X \subseteq V$ with $|X| \leq 2n - 2$ we have
$|\Gamma_G(X)| \geq (d + 1)|X|$. A tree $T$ is small if it has at
most n vertices and has maximum degree at most d. Friedman and
Pippenger (1987) proved that any $(n, d)$-expander contains every
small tree. However, their elegant proof does not seem to yield
an efficient algorithm for obtaining the tree. In this paper, we
give an alternative result that does admit a polynomial time
algorithm for finding the immersion of any small tree in subgraphs
$G$ of $(N, D, \lambda)$-graphs $\Lambda$, as long as $G$ contains
a positive fraction of the edges of $\Lambda$ and $\lambda/D$ is
small enough. In several applications of the Friedman-Pippenger
theorem, including the ones in the original paper of those
authors, the $(n, d)$-expander G is a subgraph of an $(N, D,
\lambda)$-graph as above. Therefore, our result suffices to
provide efficient algorithms for such previously non-constructive
applications. As an example, we discuss a recent result of Alon,
Krivelevich, and Sudakov concerning embedding nearly spanning
bounded degree trees, the proof of which makes use of the
Friedman-Pippenger theorem.
Our approach is based on a
reduction of the tree embedding problem to a certain online
matching problem for bipartite graphs, solved by Aggarwal et
al. (1996).
2) Dellamonica, Martin Marciniszyn, Yoshiharu Kohayakawa and Angelika Steger, The resilience of long cycles in random graphs, The Electronic Journal of Combinatorics, vol 15(1), R32.
Abstract: In this paper, we deal with the following two
notions: global resilience and local resilience. In
the former, we are interested in properties of random graphs that
are inherited by any subgraph with at least some fraction $\alpha$
of the edges of the original graph. In the latter, the subgraphs
considered are such that every vertex in the subgraph have at
least some fraction $\alpha$ of the edges of the random graph.
Let $G = G_{n, p}$ be a random graph with $p \gg n^{-1}$. We
prove that, with high probability, any subgraph of $G$ having a
fraction $(1 - w(\alpha)) (\alpha + w(\alpha)) + o(1)$ of the
edges of $G$, where $w(a) = 1 - (1 - \alpha) \lfloor (1 -
\alpha)^{-1} \rfloor$, contains a cycle of length $(1-\alpha)
n$. As for the local resilience, we have, for any $0 < \alpha <
1/2$, with high probability, the following: if $G' \subset G$ is
such that $d_{G'}(v) > \Big( \frac{1}{2} + o(1) \Big) d_G(v)$ for
all $v \in V(G)$ then $G'$ contains a cycle of length $(1 -
\alpha) n$.
1) Dellamonica, Paulo J. S. Silva, Carlos Humes Jr, Nina S. T. Hirata and Junior Barrera, An Exact Algorithm for Optimal MAE Stack Filter Design, IEEE Transactions on Image Processing, vol. 16, issue 2, pages 453-462, 2007
Also presented at the International Symposium on Mathematical Programming, Rio de Janeiro, 2006
Abstract: We propose a new algorithm for optimal MAE stack filter design. It is based on three main ingredients. First, we show that the dual of the integer programming formulation of the filter design problem is a minimum cost network flow problem. Next, we present a decomposition principle that can be used to break this dual problem into smaller subproblems. Finally, we propose a specialization of the network Simplex algorithm based on column generation to solve these smaller subproblems. Using our method, we were able to efficiently solve instances of the filter problem with window size up to 25 pixels. To the best of our knowledge, this is the largest dimension for which this problem was ever solved exactly
Conference Proceedings
Dellamonica, An asymmetric condenser, presented at LATIN 2008. Published proceedings on Lecture Notes on Computer Science, Vol. 4957, pp. 664-675, Springer, 2008.
Abstract: Condensers are functions which receive two inputs—a random string of bits chosen according to some unknown distribution and an independent uniform (short) seed—and output a string of bits which somehow preserves the randomness of the input. The parameters of interest here are the seed length, output length and how much randomness is preserved.
Here we present explicit algorithms for condensers which have constant seed size. Our constructions improve on previous constant-seed condensers of Barak et al(2003). When the input distribution has high min-entropy, we provide a condenser having optimal rate and seed chosen from $\{1, 2, 3\}$. The analysis of this construction is considerably simpler than those of previous constructions. For the low min-entropy regime, we provide a different construction which can be viewed as a pseudorandom coloring of hypergraphs. The analysis of this condenser involves a generalization of the celebrated Balog-Szemerédi-Gowers Theorem. As an example of the simplicity of the ideas behind this generalization, we improve Bourgain-Katz-Tao sum-product estimates in just a few lines.
Dellamonica, Yoshiharu Kohayakawa, Vojtěch Rödl, Andrzej Ruciński, Universality of random graphs
Abstract: For any $d \in \mathbb{N}$, with high probability, the random graph $G_{n, p}$, with $p = C(d) n^{-\frac{1}{2d}} \log^{\frac{1}{d}} n}$, contains all graphs on $n$ vertices with maximum degree at most $d$. In other words, $G_{n, p}$ is almost surely universal with respect to $n$-vertex graphs of bounded (constant) degree.
This paper was presented at SODA 2008.
Domingos Dellamonica Jr and Yoshiharu Kohayakawa, An algorithmic Friedman-Pippenger theorem on tree embeddings and applications to routing (Extended Abstract) on SODA - Proceedings of the 17th annual ACM-SIAM symposium on Discrete algorithms, Miami, 2006
A preprint of the journal version, which fixes an error in the extended abstract is listed below
Preprints
Dellamonica, Colton Magnant and Daniel M. Martin, Rainbow paths
Abstract: A $k$-rainbow path in a graph with colored edges is a path of length $k$ where each edge has a different color. In this note, we settle the problem of obtaining a constructive $k$-coloring of the edges of $K_n$ in which one may find, between any pair of vertices, a large number of internally disjoint $k$-rainbow paths. In fact, our construction obtains the largest possible number of paths. This problem was considered in a less general setting by Chartrand et al. (2007).
Submitted