Graphs are mathematical abstractions that are useful for solving many types of problems in computer science. In this dissertation, when we talk of graphs we refer to directed graphs (digraphs), which consist of a set of nodes and a set of edges between the nodes, where each edge has a direction. Numerous implementations of graphs exist in computer science however, there is a need for more systematic and complete categorisation of implementations together with some proof of correctness. Completeness is an issue because other studies only tend to discuss the useful implementations and completely or partially ignore the rest. There is also a need for a treatment of graph representations using triples instead pairs as the base component. In this dissertation, a solution to each of these deficiencies is presented. This dissertation is a taxonomic approach towards a comprehensive treatment of digraph representations. The difficulty of comparing implementations with each other is overcome by a creating a taxonomy of digraph implementations. Taxonomising digraph representations requires a systematic analysis of the two main building blocks of digraphs implementations namely maps and sets. The analysis presented in the first part of the dissertation includes a definition of the abstract data types to represent maps and sets together with a comprehensive and systematic collection of algorithms and data-structures required for the implementations thereof. These algorithms are then written and re-written in a common notation and are examined for any essential com¬ponents, differences, variations and common features. Based on this analysis the maps and sets taxonomies are presented. After the completion of maps and sets implementation foundations the dissertation continues with the main contribution: a systematic collection and implementation of other operators used for the manipulation of the base triple components of digraphs and the derivation of the the final taxonomy of digraphs by integrating the maps and sets implementations with the operators on the sets of triples. With the digraph taxonomy we can finally see relationships between implementations and we also can easily establish their similarities and differences. Furthermore, the taxonomy is also useful for further discussions, analysis and visualisation of the complete implementation topography of digraph implementations. / Dissertation (MSc (Computer Science))--University of Pretoria, 2006. / Computer Science / unrestricted

Thesis (M. Sc.)--Carleton University, 2004. / Includes bibliographical references (p. 95-99). Also available in electronic format on the Internet.

Orientador: Celia Picinin de Mello / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-08T21:07:02Z (GMT). No. of bitstreams: 1 Pedrotti_Vagner_M.pdf: 1466848 bytes, checksum: 52ed7d36d9f4f7cb6bee307b689f5f78 (MD5) Previous issue date: 2007 / Resumo: Um modulo de um grafo é um subconjunto de seus vertices que não é diferenciado, em relação à adjancencia peços demais vertices do mesmo grafo. Dado um mpodulo M de um grafo G, se todo módulo de G que intercepta M está contido nele ou o contém. M é denominado módulo forte¿Observação: O resumo, na íntegra poderá ser visualizado no texto completo da tese digital / Abstract: A module of a graph is a non distinguishable subset of nodes, regarding the nodes adjacency. Let M denote any module of a graph G. If every module of G wich overlaps M either contains M or is included in it, M is called a strong module...Note: The complete abstract is available with the full electronic digital thesis or dissertations / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Made available in DSpace on 2016-03-15T19:37:48Z (GMT). No. of bitstreams: 1 Willyan Daniel Abilhoa.pdf: 1956528 bytes, checksum: 5d317e6fd19aebfc36180735bcf6c674 (MD5) Previous issue date: 2014-02-05 / Fundação de Amparo a Pesquisa do Estado de São Paulo / Twitter is a microblog service that generates a huge amount of textual content daily. All this content needs to be explored by means of techniques, such as text mining, natural language processing and information retrieval. In this context, the automatic keyword extraction is a task of great usefulness that can be applied to indexing, summarization and knowledge extrac-tion from texts. A fundamental step in text mining consists of building a text representation model. The model known as vector space model, VSM, is the most well-known and used among these techniques. However, some difficulties and limitations of VSM, such as scalabil-ity and sparsity, motivate the proposal of alternative approaches. This dissertation proposes a keyword extraction method, called TKG (Twitter Keyword Graph), for tweet collections that represents texts as graphs and applies centrality measures for finding the relevant vertices (keywords). To assess the performance of the proposed approach, two different sets of exper-iments are performed and comparisons with TF-IDF and KEA are made, having human clas-sifications as benchmarks. The experiments performed showed that some variations of TKG are invariably superior to others and to the algorithms used for comparisons. / O Twitter é um serviço de microblog que gera um grande volume de dados textuais. Todo esse conteúdo precisa ser explorado por meio de técnicas de mineração de textos, processamento de linguagem natural e recuperação de informação com o objetivo de extrair um conhecimento que seja útil de alguma forma ou em algum processo. Nesse contexto, a extração automática de palavras-chave é uma tarefa que pode ser usada para a indexação, sumarização e compreensão de documentos. Um passo fundamental nas técnicas de mineração de textos consiste em construir um modelo de representação de documentos. O modelo chamado mode-lo de espaço vetorial, VSM, é o mais conhecido e utilizado dentre essas técnicas. No entanto, algumas dificuldades e limitações do VSM, tais como escalabilidade e esparsidade, motivam a proposta de abordagens alternativas. O presente trabalho propõe o método TKG (Twitter Keyword Graph) de extração de palavras-chave de coleções de tweets que representa textos como grafos e aplica medidas de centralidade para encontrar vértices relevantes, correspondentes às palavras-chave. Para medir o desempenho da abordagem proposta, dois diferentes experimentos são realizados e comparações com TF-IDF e KEA são feitas, tendo classifica-ções humanas como referência. Os experimentos realizados mostraram que algumas variações do TKG são superiores a outras e também aos algoritmos usados para comparação.