Ir al contenido

Documat


Aspects of random graphs: colourings, walkers and hamiltonian cycles.

  • Autores: Xavier Perez Gimenez
  • Directores de la Tesis: Josep Díaz Cort (dir. tes.) Árbol académico
  • Lectura: En la Universitat Politècnica de Catalunya (UPC) ( España ) en 2007
  • Idioma: español
  • Tribunal Calificador de la Tesis: Marc Noy Serrano (presid.) Árbol académico, María José Serna Iglesias (secret.) Árbol académico, Colin McDiarmid (voc.) Árbol académico, Nick Wormald (voc.) Árbol académico, Lefteris Kirousis (voc.) Árbol académico
  • Texto completo no disponible (Saber más ...)
  • Resumen
    • This dissertation presents the author's work in some problems involving different models of random graphs, First it contains a technical contribution towards solving the open problem of deciding whether with high probability a random $5$-regular graph can be coloured with three colours. Next, the author proposes a model for the establishment and maintenance of communication between agents in a \emph{mobile ad-hoc network} ({\sc manet}), which is called the {\em walkers model}. We assume that the agents move through a fixed environment modelled by a motion graph, and are able to communicate only if they are at a distance of at most $d$. As the agents move randomly, we analyse how the connectivity between a set of $w$ agents evolves over time, asymptotically for a large number $N$ of vertices, when $w$ also grows large. The particular topologies of the environment which are studied here are the cycle and the toroidal grid. For the latter, the results apply under any $\ell_p$-normed distance, for $1\leq p\leq\infty$. Then, the dissertation follows with a continuous counterpart of the walkers model. Namely, it presents a model for {\sc manet}s based on random geometric graphs over the $2$-dimensional unit torus, where each node moves under the {\em random walk} mobility model. More precisely, our model starts from a random geometric graph over the torus \UT, with $n$ nodes and radius exactly at the connectivity threshold $r_c$. Then each node chooses independently a random angle in $[0,2\pi)$ and moves for a number $m$ of steps a fixed distance $s>0$ in that direction. After these steps, each node again chooses a new angle and starts moving in that new direction, repeating the change of direction every $m$ steps. We compute the expected number of steps for which the resulting graph stays connected or disconnected. In addition, for static random geometric graphs with radius at the connectivity threshold $r_c$, we provide asymptotic expressions on the probability of


Fundación Dialnet

Mi Documat

Opciones de tesis

Opciones de compartir

Opciones de entorno