Muitos dos sistemas de computação existentes atualmente são concorrentes, ou seja, neles constam diversas entidades que, ao mesmo tempo, operam sobre um conjunto de recursos compartilhados. Nesse contexto, devemos controlar a concorrência das diversas operações realizadas, ou então a interferência entre elas poderia causar inconsistências nos recursos compartilhados ou nas próprias operações realizadas. Nesse texto, vamos tratar especificamente de estruturas de dados concorrentes, ou seja, estruturas de dados cujas operações associadas -- consideramos inserção, remoção e busca -- sejam passíveis de execução simultânea por diversas entidades. Tendo em vista o controle da concorrência, vamos adotar uma abordagem baseada no emprego de locks, uma primitiva de sincronização muito usual na literatura. Nossa discussão será apresentada em termos de certas estruturas de dados chamadas skip graphs, que têm propriedades interessantes para outros contextos, como o contexto de sistemas distribuídos. / Many existing computer systems are concurrent, or, in other words, they are composed of many entities that, at the same time, operate over some set of shared resources. In this context, we must control the concurrency of the operations, otherwise the interference between them could cause inconsistencies in the shared resources or in the operations themselves. In this text, we specifically discuss concurrent data structures, or, in other words, data structures over which the associated operations -- we consider insertion, removal and search -- could be executed simultaneously by various entities. In order to control the concurrency, we will employ an aproach based on the use of locks, a widely known synchronization primitive in the literature. Our discussion will be presented in terms of data structures called skip graphs, which have interesting properties in other contexts, as the context of distributed systems.

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第23322号 / 情博第758号 / 新制||情||129(附属図書館) / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 永持 仁, 教授 太田 快人, 教授 山下 信雄 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

There are different models, which describe conditional independence induced by multivariate distributions. Models such as Undirected Graphs, Directed Acyclic Graphs, Essential Graphs and Annotated Graphs are introduced and compared in this thesis. The focus is put on annotated graphs. It is shown that annotated graphs represent equivalence classes of DAG-representable relations. An algorithm for reconstruction of an annotated graph from an essential graph as well as the algorithm for the inverse procedure are given. Some properties of a characteristic imset, which is a non-graphical representation, are discussed. A relationship between annotated graphs and characteristic imsets is investigated, an algorithm, which reconstructs an annotated graph from a characteristic imset is given. Powered by TCPDF (www.tcpdf.org)

No description available.

>Magister Scientiae - MSc / For integers n, k 2:: 1, and k ~ n, the graph r~has vertices the 2n vectors of lF2 and adjacency defined by two vectors being adjacent if they differ in k coordinate positions. In particular, r~is the classical n-cube, usually denoted by Hl (n, 2). This study examines the codes (both binary and p-ary for p an odd prime) of the row span of adjacency and incidence matrices of these graphs. We first examine codes of the adjacency matrices of the n-cube. These have been considered in [14]. We then consider codes generated by both incidence and adjacency matrices of the Hamming graphs Hl(n,3) [12]. We will also consider codes of the line graphs of the n-cube as in [13]. Further, the automorphism groups of the codes, designs and graphs will be examined, highlighting where there is an interplay. Where possible, suitable permutation decoding sets will be given.

A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γt(G) is the minimum cardinality of a total dominating set of G. Let G be a connected spanning subgraph of Ks,s, and let H be the complement of G relative to Ks,s; that is, Ks,s, = G ⊕ H is a factorization of Ks,s. The graph G is k-supercritical relative to Ks,s, if γt(G) = k and γ1(G + e) = k - 2 for all e ∈ E(H). Properties of k-supercritical graphs are presented, and k-supercritical graphs are characterized for small k.

This thesis consists of two papers, enumerated by Roman numerals. The main focus is on the spectral theory of <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?n" />-Laplacians. Here, an <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?n" />-Laplacian, for integer <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?n" />, refers to a metric graph equipped with a differential operator whose differential expression is the <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?2n" />-th derivative. In Paper I, a classification of all vertex conditions corresponding to self-adjoint <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?n" />-Laplacians is given, and for these operators, a secular equation is derived. Their spectral asymptotics are analysed using the fact that the secular function is close to a trigonometric polynomial, a type of almost periodic function. The notion of the quasispectrum for <img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?n" />-Laplacians is introduced, identified with the positive roots of the associated trigonometric polynomial, and is proved to be unique. New results about almost periodic functions are proved, and using these it is shown that the quasispectrum asymptotically approximates the spectrum, counting multiplicities, and results about asymptotic isospectrality are deduced. The results obtained on almost periodic functions have wider applications outside the theory of differential operators. Paper II deals more specifically with bi-Laplacians (<img src="http://www.diva-portal.org/cgi-bin/mimetex.cgi?n=2" />), and a notion of standard conditions is introduced. Upper and lower estimates for the spectral gap --- the difference between the two lowest eigenvalues - for these standard conditions are derived. This is achieved by adapting the methods of graph surgery used for quantum graphs to fourth order differential operators. It is observed that these methods offer stronger estimates for certain classes of metric graphs. A geometric version of the Ambartsumian theorem for these operators is proved.

Graphs provide powerful abstractions, and are widely used in different areas. There has been an increasing demand in using the graph data model to represent data in many applications such as network management, web page analysis, knowledge graphs, social networks. These graphs are usually dynamic and represent the time evolving relationships between entities. Enforcing and maintaining data quality in graphs is a critical task for decision making, operational efficiency and accurate data analysis as recent studies have shown that data scientists spend 60-80% of their time cleaning and organizing data [2]. This effort motivates the need for effective data cleaning tools to reduce the user burden. The study of data quality management focuses along a set of dimensions, including data consistency, data deduplication, information completeness, data currency, and data accuracy. Achieving all these data characteristics is often not possible in practice due to personnel costs, and for performance reasons. In this thesis, we focus on tackling three problems in two data quality dimensions: data consistency and data deduplication. To address the problem of data consistency over temporal graphs, we present a new class of data dependencies called Temporal Graph Functional Dependency (TGFDs). TGFDs generalize functional dependencies to temporal graphs as a sequence of graph snapshots that are induced by time intervals, and enforce both topological constraints and attribute value dependencies that must be satisfied by these snapshots. We establish the complexity results for the satisfiability and implication problems of TGFDs. We propose a sound and complete axiomatization system for TGFDs. We also present efficient parallel algorithms to detect inconsistencies in temporal graphs as violations of TGFDs. To address the data deduplication problem, we first address the problem of key discovery for graphs. Keys for graphs use topology and value constraints to uniquely identify entities in a graph database and keys are the main tools for data deduplication in graphs. We present two properties that define a key, including minimality and support and an algorithm to mine keys over graphs via frequent subgraph expansion. However, existing key constraints identify entities by enforcing label equality on node types. These constraints can be too restrictive to characterize structures and node labels that are syntactically different but semantically equivalent. Lastly, we propose a new class of key constraints, Ontological Graph Keys (OGKs) that extend conventional graph keys by ontological subgraph matching between entity labels and an external ontology. We study the entity matching problem with OGKs. We develop efficient algorithms to perform entity matching based on a Chase procedure. The proposed dependencies and algorithms in this thesis improve consistency detection in temporal graphs, automate the discovery of keys in graphs, and enrich the semantic expressiveness of graph keys. / Dissertation / Doctor of Science (PhD)

Quantum walks have been utilized by many quantum algorithms which provide improved performance over their classical counterparts. Quantum search algorithms, the quantum analogues of spatial search algorithms, have been studied on a wide variety of structures. We study quantum walks and searches on the Cayley graphs of finitely-generated free groups. Return properties are analyzed via Green’s functions, and quantum searches are examined. Additionally, the stopping times and success rates of quantum searches on random networks are experimentally estimated. / Mathematics

Level sets are extensively used for the visualization of scalar fields. The Reeb graph of a scalar function tracks the evolution of the topology of its level sets. It is obtained by mapping each connected component of a level set to a point. The Reeb graph and its loop-free version called the contour tree serve as an effective user interface for selecting meaningful level sets and for designing transfer functions for volume rendering. It also finds several other applications in the field of scientific visualization. In this thesis, we focus on designing algorithms for efficiently computing the Reeb graph of scalar functions and using the Reeb graph for effective visualization of scientific data. We have developed three algorithms to compute the Reeb graph of PL functions defined over manifolds and non-manifolds in any dimension. The first algorithm efficiently tracks the connected components of the level set and has the best known theoretical bound on the running time. The second algorithm, utilizes an alternate definition of Reeb graphs using cylinder maps, is simple to implement and efficient in practice. The third algorithm aggressively employs the efficient contour tree algorithm and is efficient both theoretically, in terms of the worst case running time, and practically, in terms of performance on real-world data. This algorithm has the best performance among existing methods and computes the Reeb graph at least an order of magnitude faster than other generic algorithms. We describe a scheme for controlled simplification of the Reeb graph and two different graph layout schemes that help in the effective presentation of Reeb graphs for visual analysis of scalar fields. We also employ the Reeb graph in four different applications – surface segmentation, spatially-aware transfer function design, visualization of interval volumes, and interactive exploration of time-varying data. Finally, we introduce the notion of topological saliency that captures the relative importance of a topological feature with respect to other features in its local neighborhood. We integrate topological saliency with Reeb graph based methods and demonstrate its application to visual analysis of features.