BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Given a class of graphs G closed under taking minors, we study the maximum degree Δ_n of random graphs from G with n vertices. We prove several lower and upper bounds that hold with high probability. Among other results, we find classes of graphs providing orders of magnitude for Δ_n not observed before, such us \log n/ \log \log \log n and \log n/ \log \log \log \log n.
We present a domain-independent algorithm that computes macros in a novel way. Our algorithm computes macros "on-the-fly" for a given set of states and does not require previously learned or inferred information, nor prior domain knowledge. The algorithm is used to define new domain-independent tractable classes of classical planning that are proved to include \emph{Blocksworld-arm} and \emph{Towers of Hanoi}.
It is shown that the number of labelled graphs with n vertices that can be embedded in the orientable surface S_g of genus g grows asymptotically like c(g)n5(g−1)/2−1γnn! where c(g)>0, and γ≈27.23 is the exponential growth rate of planar graphs. This generalizes the result for the planar case g=0, obtained by Gimenez and Noy. An analogous result for non-orientable surfaces is obtained. In addition, it is proved that several parameters of interest behave asymptotically as in the planar case. It follows, in particular, that a random graph embeddable in S_g has a unique 2-connected component of linear size with high probability.
We prove that the maximum degree Δn of a random series-parallel graph with n vertices satisfies Δn/logn→c in probability, and EΔn∼clogn for a computable constant c>0. The same result holds for outerplanar graphs.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.