In a search game, a seeker searches for a hider in some space. The seeker wishes to find the hider as quickly as possible, and the hider wishes to avoid capture as long as possible. In this paper, I will focus on the case where the search space is a star, and the only information the seeker has is the speed of the hider. I will provide algorithms for some cases where the seeker is guaranteed to find the hider and prove optimality for some of these cases. Also, I will look at some cases where the hider can avoid capture indefinitely. I will also present some results for searching on trees.

We examine the problem of counting interval graphs. We answer the question posed by Hanlon, of whether the formal power series generating function of the number of interval graphs on n vertices has a positive radius of convergence. We have found that it is zero. We have obtained a lower bound and an upper bound on the number of interval graphs on n vertices. We also study the application of interval graphs to the dynamic storage allocation problem. Dynamic storage allocation has been shown to be NP-complete by Stockmeyer. Coloring interval graphs on-line has applications to dynamic storage allocation. The most colors used by Kierstead's algorithm is 3 ω -2, where ω is the size of the largest clique in the graph. We determine a lower bound on the colors used. One such lower bound is 2 ω -1.

Not available / text

Community, a notion transversal to all areas of Social Network Analysis, has drawn tremendous amount of attention across the sciences in the past decades. Numerous attempts to characterize both the sociological embodiment of the concept as well as its observable structural manifestation in the social network have to this date only converged in spirit. No formal consensus has been reached on the quantifiable aspects of community, despite it being deeply linked to topological and dynamic aspects of the underlying social network. Presenting a fresh approach to the evaluation of communities, this thesis introduces and builds upon the cohesion, a novel metric which captures the intrinsic quality, as a community, of a set of nodes in a network. The cohesion, defined in terms of social triads, was found to be highly correlated to the subjective perception of communitiness through the use of a large-scale online experiment in which users were able to compute and rate the quality of their social groups on Facebook. Adequately reflecting the complexity of social interactions, the problem of finding a maximally cohesive group inside a given social network is shown to be NP-hard. Using a heuristic approximation algorithm, applications of the cohesion to broadly different use cases are highlighted, ranging from its application to network visualization, to the study of the evolution of agreement groups in the United States Senate, to the understanding of the intertwinement between subjects' psychological traits and the cohesive structures in their social neighborhood. The use of the cohesion proves invaluable in that it offers non-trivial insights on the network structure and its relation to the associated semantic.

The work in this thesis can be divided into two different parts. In the first part, we suggest an approximate edge 3-coloring polynomial time algorithm for cubic graphs. For any cubic graph with n vertices, using this coloring algorithm, we get an edge 3-coloring with at most n/3 error vertices. In the second part, we study Jim Propp's Rotor-Router model on some non-bipartite graph. We find the difference between the number of chips at vertices after performing a walk on this graph using Propp model and the expected number of chips after a random walk. It is known that for line of integers and d-dimenional grid, this deviation is constant. However, it is also proved that for k-ary infinite trees, for some initial configuration the deviation is no longer a constant and say it is D. We present a similar study on some non-bipartite graph constructed from k-ary infinite trees and conclude that for this graph with the same initial configuration, the deviation is almost (k²)D.

Thesis (M.S.)--University of Texas at El Paso, 2007. / Title from title screen. Vita. CD-ROM. Includes bibliographical references. Also available online.

Thesis (Ph. D.)--University of Texas at Austin, 2007. / Vita. Includes bibliographical references.

Thesis (Ph.D.) -- Mississippi State University. Department of Computer Science and Engineering. / Title from title screen. Includes bibliographical references.

Graph augmentation concerns the addition of edges to a graph to satisfy some connectivity property of a graph. Previous research in this field has been preoccupied with edge augmentation; however the research in this document focuses on the addition of vertices to a graph to satisfy a specific connectivity property: ensuring that all the nodes of the graph are contained within cycles. A distinction is made between graph augmentation (edge addition), and graph enlargement (vertex addition). This document expands on previous research into a graph matching problem known as the “shoe matching problem” and the role of a graph enlargement algorithm in finding this solution. The aim of this research was to develop new and efficient algorithms to solve the graph enlargement problem as applied to the shoe matching problem and to improve on the naïve algorithm of Sanders. Three new algorithms focusing on graph enlargement and the shoe matching problem are presented, with positive results overall. The new enlargement algorithms: cost-optimised, matrix, and subgraph, succeeded in deriving the best result (least number of total nodes required) in 37%, 53%, and 57% of cases respectively (measured across 120 cases). In contrast, Sanders’s algorithm has a success rate of only 20%; thus the new algorithms have a varying success rate of approximately 2 to 3 times that of Sanders’s algorithm. / Computing / M. Sc. Computing

La notion de communauté, transverse à  l'analyse des réseaux sociaux, a attiré une attention grandissante à  travers les sciences ces dix dernières années. Les nombreuses tentatives pour modéliser aussi bien l'incarnation sociologiquedu concept aussi bien que sa manifestation structurelle dans le réseau social n'ont jusqu'à  présent que vaguement convergé. Aucun consensus formel n'a été atteint sur les aspects quantifiables de la communauté, et ceci malgré lesliens forts la reliant aux dimensions dynamique et topologique du réseau sous-jacent.Présentant une approche novatrice à  l'évaluation des communautés, cette thèse introduit et se base sur la cohésion, une métrique qui capture la qualitéintrinsèque, en tant que communauté, d'un ensemble de sommets dans un réseau. Il a été montré au travers d'une experience à  large échelle, dans laquelle les individus sondés ont pu noter l'aspect communautaires de groupes d'amis leur étant présentés, que la cohésion, définie en lien avec la notion de triades sociales, est fortement correlée à  la perception subjective de la communauté. Reflétant la complexité des interactions sociales, il est démontré que leproblème de trouver des communautés maximalement cohésive est NP-dur. En utilisant une heuristique approximant les résultats de ce problème, un certain nombre d'applications de la cohésion à  des données réelles sont mises en avant: de son application à  la visualisation de réseaux complexes, à  l'étude de l'évolution des groupes d'agrément du sénat états-unien, à  la compréhesion des liens entre psychologie et structure du réseau social.L'utilisation de la cohésion apporte un éclairage non trivial dans l'étude de la structure des grands réseaux de terrain et dans la relation entre structure et sémantique. / Community, a notion transversal to all areas of Social Network Analysis, has drawn tremendous amount of attention across the sciences in the past decades. Numerous attempts to characterize both the sociological embodiment of the concept as well as its observable structural manifestation in the social network have to this date only converged in spirit. No formal consensus has been reached on the quantifiable aspects of community, despite it being deeply linked to topological and dynamic aspects of the underlying social network. Presenting a fresh approach to the evaluation of communities, this thesis introduces and builds upon the cohesion, a novel metric which captures the intrinsic quality, as a community, of a set of nodes in a network. The cohesion, defined in terms of social triads, was found to be highly correlated to the subjective perception of communitiness through the use of a large-scale online experiment in which users were able to compute and rate the quality of their social groups on Facebook. Adequately reflecting the complexity of social interactions, the problem of finding a maximally cohesive group inside a given social network is shown to be NP-hard. Using a heuristic approximation algorithm, applications of the cohesion to broadly different use cases are highlighted, ranging from its application to network visualization, to the study of the evolution of agreement groups in the United States Senate, to the understanding of the intertwinement between subjects' psychological traits and the cohesive structures in their social neighborhood. The use of the cohesion proves invaluable in that it offers non-trivial insights on the network structure and its relation to the associated semantic.