Backbone Colouring of Graphs

Consider an undirected graph G and a subgraph of G, H. A q-backbone k-colouring of (G,H) is a mapping f: V(G) {1, 2, ..., k} such that G is properly coloured and for each edge of H, the colours of its endpoints differ by at least q. The minimum number k for which there is a backbone k-colouring of (G,H) is the backbone chromatic number, BBCq(G,H). It has been proved that backbone k-colouring of (G,T) is at most 4 if G is a connected C4-free planar graph or non-bipartite C5-free planar graph or Cj-free, j∈{6,7,8} planar graph without adjacent triangles. In this thesis we improve the results mentioned above and prove that 2-backbone k-colouring of any connected planar graphs without adjacent triangles is at most 4 by using a discharging method. In the second part of this thesis we further improve these results by proving that for any graph G with χ(G) ≥ 4, BBC(G,T) = χ(G). In fact, we prove the stronger result that a backbone tree T in G exists, such that ∀ uv ∈ T, |f(u)-f(v)|=2 or |f(u)-f(v)| ≥ k-2, k = χ(G). For the case that G is a planar graph, according to Four Colour Theorem, χ(G) = 4; so, BBC(G,T) = 4.

Using PageRank Algorithm in Analyzing Dictionary Graphs and PageRank in Dynamic Graphs

In this thesis we are going to analyze the dictionary graphs and some other kinds of graphs using the PagerRank algorithm. We calculated the correlation between the degree and PageRank of all nodes for a graph obtained from Merriam-Webster dictionary, a French dictionary and WordNet hypernym and synonym dictionaries. Our conclusion was that PageRank can be a good tool to compare the quality of dictionaries. We studied some artificial social and random graphs. We found that when we omitted some random nodes from each of the graphs, we have not noticed any significant changes in the ranking of the nodes according to their PageRank. We also discovered that some social graphs selected for our study were less resistant to the changes of PageRank.

Agreement to undertake construction and complete the road in accordance with the engineer or the Port Robinson and Thorold macadamized road

Agreement to undertake construction and complete the road in accordance with the engineer or the Port Robinson and Thorold macadamized road. This is signed by John Williams, Aug. 11, 1855.

Diagrams (charts and graphs) made into a booklet with a newspaper cover

Diagrams (charts and graphs) made into a booklet with a newspaper cover. This booklet contains cross sections of the back ditch on the south side of the Welland Canal feeder, west of the Marshville culverts (45 pages, hand drawn). This was created by Fred Holmes, Oct. 3, 1857.

Charts and graphs of cross sections from Brown’s ditch culvert to the main drain

Charts and graphs of cross sections from Brown’s ditch culvert to the main drain, cross sections from the feeder on the road allowance between lots 26 and 27 in the 5th concession of Humberstone, Cross sections of the main drain from Lyons Creek culvert to the road allowance between lots 7 and 8 in Wainfleet and cross selections of the old ditch on the west side of the road allowance between lots 17 and 18 in the 3rd concession in Wainfleet (8 pages, hand drawn), n.d.

Chart containing the statement of amount required to complete the canal

Chart containing the statement of amount required to complete the canal, March 15, 1848.

The mexican war and its warriors : comprising a complete history of all the operations of the American armies in Mexic...

UANL

Collection complete des oeuvres de M. de Crebillon le Fils

UANL

Matching Markets under (In)complete Information

We are the first to introduce incomplete information to centralized many-to-one matching markets such as those to entry-level labor markets or college admissions. This is important because in real life markets (i) any agent is uncertain about the other agents' true preferences and (ii) most entry-level matching is many-to-one (and not one-to-one). We show that for stable (matching) mechanisms there is a strong and surprising link between Nash equilibria under complete information and Bayesian Nash equilibria under incomplete information. That is,given a common belief, a strategy profile is a Bayesian Nash equilibrium under incomplete information in a stable mechanism if and only if, for any true profile in the support of the common belief, the submitted profile is a Nash equilibrium under complete information at the true profile in the direct preference revelation game induced by the stable mechanism. This result may help to explain the success of stable mechanisms in these markets.

Grammaire latine complete

UANL

Shakespeare : complete works

UANL

The Complete Confectioner Pastry-Cook and Baker : plain and practical directions for making confectionary and pastry, and for baking...

UANL

A randomized controlled trial evaluating the quality of life and the sense of coherence in seniors wearing complete conventional dentures or mandibular two-implant overdentures

La supériorité des prothèses mandibulaires retenues par deux implants (IODs) sur les prothèses conventionnelles (CDs) nécessitent d’être éclaircies notamment en rapport à leur influence sur la qualité de vie reliée à la santé bucco-dentaire (OHRQoL) ainsi que sur la stabilité de cet effet de traitement. De plus, l’influence des facteurs psychologiques, tel que le sens de cohérence (SOC), sur l’effet de traitement reste encore inconnue. Le but de cette étude est de déterminer l’amplitude de l’influence du port des IODs et des CDs sur l’OHRQoL et d’évaluer la stabilité de l’effet de traitement dans le temps, tout en prenant en considération le niveau du SOC. MÉTHODOLOGIE: Des participants édentés (n=172, âge moyen 71, SD = 4.5) ayant reçu des CDs ou des IODs ont été suivis sur une période de deux ans. L’OHRQoL a été évaluée à l’aide du questionnaire « Oral Health Impact Profile (OHIP -20) » et ce avant le traitement et à chacun des deux suivis. Le SOC a été évalué à l’aide du questionnaire « The Orientation to Life (SOC -13) » à chacun des deux suivis. Des analyses statistiques ont été effectuées pour évaluer les différences intra et entre groupes (analyses statistiques descriptives, bivariées et multivariées). RÉSULTATS: Une amélioration statistiquement significative de l’OHRQoL entre les statuts avant et après traitement a été notée dans les deux groupes (Wilks’s Lambda = 0.473, F (1,151) = 157.31, p < 0.0001). L’amplitude de l’effet du traitement IOD est 1.5 fois plus grande que celle du traitement CD. Ces résultats ont été stables pendant les deux années d’étude et ils n’ont pas été influencés par le SOC. CONCLUSION: Le traitement IOD amène une meilleure OHRQoL à long terme en comparaison avec le traitement CD et ce sans influence du niveau du SOC. Ces résultats sont cliniquement significatifs et confirment la supériorité des IODs sur les CDs.

Rétro ingénierie des modèles d’objets dynamiques pour JavaScript

La compréhension des objets dans les programmes orientés objet est une tâche impor- tante à la compréhension du code. JavaScript (JS) est un langage orienté-objet dyna- mique, et son dynamisme rend la compréhension du code source très difficile. Dans ce mémoire, nous nous intéressons à l’analyse des objets pour les programmes JS. Notre approche construit de façon automatique un graphe d’objets inspiré du diagramme de classes d’UML à partir d’une exécution concrète d’un programme JS. Le graphe résul- tant montre la structure des objets ainsi que les interactions entre eux. Notre approche utilise une transformation du code source afin de produire cette in- formation au cours de l’exécution. Cette transformation permet de recueillir de l’infor- mation complète au sujet des objets crées ainsi que d’intercepter toutes les modifications de ces objets. À partir de cette information, nous appliquons plusieurs abstractions qui visent à produire une représentation des objets plus compacte et intuitive. Cette approche est implémentée dans l’outil JSTI. Afin d’évaluer l’utilité de l’approche, nous avons mesuré sa performance ainsi que le degré de réduction dû aux abstractions. Nous avons utilisé les dix programmes de réfé- rence de V8 pour cette comparaison. Les résultats montrent que JSTI est assez efficace pour être utilisé en pratique, avec un ralentissement moyen de 14x. De plus, pour 9 des 10 programmes, les graphes sont suffisamment compacts pour être visualisés. Nous avons aussi validé l’approche de façon qualitative en inspectant manuellement les graphes gé- nérés. Ces graphes correspondent généralement très bien au résultat attendu. Mots clés: Analyse de programmes, analyse dynamique, JavaScript, profilage.

Clique Irreducibility of Some Iterative Classes of Graphs

In this paper, two notions, the clique irreducibility and clique vertex irreducibility are discussed. A graph G is clique irreducible if every clique in G of size at least two, has an edge which does not lie in any other clique of G and it is clique vertex irreducible if every clique in G has a vertex which does not lie in any other clique of G. It is proved that L(G) is clique irreducible if and only if every triangle in G has a vertex of degree two. The conditions for the iterations of line graph, the Gallai graphs, the anti-Gallai graphs and its iterations to be clique irreducible and clique vertex irreducible are also obtained.