article · 2010

A randomized embedding algorithm for trees

Benny Sudakov, Jan Vondrák

Cited by 0Abstract and details only

Abstract

In this paper, we propose a simple and natural randomized algorithm to embed a tree T in a given graph G. The algorithm can be viewed as a “self-avoiding tree-indexed random walk”. The order of the tree T can be as large as a constant fraction of the order of the graph G, and the maximum degree of T can be close to the minimum degree of G. We show that our algorithm works in a variety of interesting settings. For example, we prove that any graph of minimum degree d without 4-cycles contains every tree of order d2 and maximum degree at most d−2d−2. As there exist d-regular graphs without 4-cycles and with O(d2) vertices, this result is optimal up to constant factors. We prove similar nearly tight results for graphs of given girth and graphs with no complete bipartite subgraph Ks,t.

Cite this paper

APA 7

Benny Sudakov, J. V. (2010). A randomized embedding algorithm for trees.

MLA 9

Benny Sudakov, Jan Vondrák. “A randomized embedding algorithm for trees.” 2010.

Chicago

Benny Sudakov, Jan Vondrák. 2010. “A randomized embedding algorithm for trees.”

Harvard

Benny Sudakov, J.V. (2010) ‘A randomized embedding algorithm for trees’.

BibTeX

@article{bennysudakov2010randomized,
  title = {{A randomized embedding algorithm for trees}},
  author = {Benny Sudakov, Jan Vondrák},
  year = {2010}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.