Relevant bibliographies by topics / Directed graphs / Dissertations / Theses
To see the other types of publications on this topic, follow the link: Directed graphs.

Dissertations / Theses on the topic 'Directed graphs'

Author: Grafiati
Published: 4 June 2021
Last updated: 29 July 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 dissertations / theses for your research on the topic 'Directed graphs.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.

1

Myers, Joseph Samuel. "Extremal theory of graph minors and directed graphs." Thesis, University of Cambridge, 2003. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.619614.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Marr, Alison M. "Labelings of directed graphs /." Available to subscribers only, 2007. http://proquest.umi.com/pqdweb?did=1362527421&sid=22&Fmt=2&clientId=1509&RQT=309&VName=PQD.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Counts, Jared B. "Knitting with directed graphs." Thesis, Massachusetts Institute of Technology, 2018. http://hdl.handle.net/1721.1/119547.

Full text
Abstract:
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2018.
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 67-68).
Knitting has historically been communicated by its means of construction. For hand knitting, this is typically a list of instructions or a pictorial grid with knitting symbols. For machine knitting, a similar pictorial grid is used to express needle-level instructions. However, these formats suffer by the nature of their tight coupling with the method used to construct the garments they represent. Alternatively, we use Knit Meshes, which represent knitting structures by their geometry separate from a directed graph description of their topology. This thesis presents an algorithm that can generate a natural, deformed two-dimensional layout of Knit Meshes as well as a conversion pipeline that converts written hand knitting instructions to and from Knit Meshes and an algorithm that converts certain Knit Meshes into knitting machine code.
by Jared B. Counts.
M. Eng.
APA, Harvard, Vancouver, ISO, and other styles
4

Townsend, Timothy Duncan. "Extremal problems on graphs, directed graphs and hypergraphs." Thesis, University of Birmingham, 2016. http://etheses.bham.ac.uk//id/eprint/6453/.

Full text
Abstract:
This thesis is concerned with extremal problems on graphs and similar structures. We first study degree conditions in uniform hypergraphs that force matchings of various sizes. Our main result in this area improves bounds of Markstrom and Rucinski on the minimum d-degree which forces a perfect matching in a k-uniform hypergraph on n vertices. We then study connectivity conditions in tournaments that ensure the existence of partitions of the vertex set that satisfy various properties. In 1982 Thomassen asked whether every sufficiently strongly connected tournament T admits a partition of its vertex set into t vertex classes such that the subtournament induced on T by each class is strongly k-connected. Our main result in this area implies an affirmative answer to this question. Finally we investigate the typical structure of graphs and directed graphs with some forbidden subgraphs. We answer a question of Cherlin by finding the typical structure of triangle-free oriented graphs. Moreover, our results generalise to forbidden transitive tournaments and forbidden oriented cycles of any order, and also apply to digraphs. We also determine, for all k > 5, the typical structure of graphs that do not contain an induced 2k-cycle. This verifies a conjecture of Balogh and Butterfield.
APA, Harvard, Vancouver, ISO, and other styles
5

Kelly, Luke Tristian. "On cycles in directed graphs." Thesis, University of Birmingham, 2010. http://etheses.bham.ac.uk//id/eprint/940/.

Full text
Abstract:
The main results of this thesis are the following. We show that for each alpha > 0 every sufficiently large oriented graph G with minimum indegree and minimum outdegree at least 3 |G| / 8 + alpha |G| contains a Hamilton cycle. This gives an approximate solution to a problem of Thomassen. Furthermore, answering completely a conjecture of Haggkvist and Thomason, we show that we get every possible orientation of a Hamilton cycle. We also deal extensively with short cycles, showing that for each l > 4 every sufficiently large oriented graph G with minimum indegree and minimum outdegree at least |G| / 3 + 1 contains an l-cycle. This is best possible for all those l > 3 which are not divisible by 3. Surprisingly, for some other values of l, an l-cycle is forced by a much weaker minimum degree condition. We propose and discuss a conjecture regarding the precise minimum degree which forces an l-cycle (with l > 3 divisible by 3) in an oriented graph. We also give an application of our results to pancyclicity.
APA, Harvard, Vancouver, ISO, and other styles
6

Brunner, Wolfgang. "Cyclic level drawings of directed graphs /." kostenfrei, 2010. http://www.opus-bayern.de/uni-passau/volltexte/2010/1796/.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Garcia, Gasulla Dario. "Link prediction in large directed graphs." Doctoral thesis, Universitat Politècnica de Catalunya, 2015. http://hdl.handle.net/10803/299070.

Full text
Abstract:
The first chapter introduces an approach to machine learning (ML) were data is understood as a network of connected entities. This strategy seeks inter-entity information for knowledge discovery, in contrast with traditional intra-entity approaches based on instances and their features. We discuss the importance of this connectivist ML (which we refer to as graph mining) in the current context where large, topology-based data sets have been made available. Chapter ends by introducing the Link Prediction (LP) problem, together with its current computational and performance limitations. The second chapter discusses early contributions to graph mining, and introduces problems frequently tackled through this paradigm. Later the chapter focuses on the state-of-the-art of LP. It presents three different approaches to the problem of finding links in a relational set, and argues about the importance of the most computationally scalable one: similarity-based algorithms. It categorizes similarity-based algorithms in three types of LP scores. For the most scalable type, local similarity-based algorithms, the chapter identifies and formally describes the most competitive proposals according to the bibliography. Chapter three analyses the LP problem, partly as a classic binary classification problem. A list of graph properties such as directionality, weights and time are discussed in the context of LP. Follows a formal time and space complexity analysis of similarity-based scores of LP. The chapter ends with an study of the class imbalance found in LP problems. In chapter four a novel similarity-based score of LP is introduced. The chapter first elaborates on the importance of hierarchies for representing knowledge through directed graphs. Several modifications to the proposed score are also defined. This chapter presents a modified version of the most competitive undirected scores of LP, to adapt them to directed graphs. The evaluation methodologies of LP are analyzed in the fifth chapter. It starts by discussing the problem of evaluating domains with a huge class imbalance, identifying the most appropriate methodologies for it. A modification of the most appropriate evaluation methodology according to the bibliography is presented, with the goal of focusing on relevant predictions. Follows a discussion on the faithful estimation of the precision of predictors. Chapter six describes the graphs used for score evaluation, as well as how data was transformed into a directed graph. Reasons on why these particular domains were chosen are given, making a special case of webgraphs and their well known relation with hierarchies. The most basic properties of each resultant graph are shown. Tests performed are presented in chapter seven. The three most competitive LP scores currently available are tested among themselves, and against a proposed version of those same scores for directed graphs. Our proposed score and its modifications are tested against the scores obtaining the best results in the previous tests. The case of LP in webgraphs is considered separately, testing six different webgraphs. The chapter ends with a discussion on the limitations of this formal analysis, showing examples of predictions obtained. Chapter eight includes the computational aspects of the work done. It starts with a discussion on the importance of memory management for determining the computational cost of LP algorithms. A proposal on how to reduce this cost through precision reduction is presented. Follows a section focused on the parallelization of code, which includes two different implementations on one graph-specific programming model (Pregel) and on one generic programming model (OpenMP). The chapter ends with a specification of the computational resources used for the tests done. The conclusions of this thesis proposal are presented in nine. Chapter ten contains several future lines of work.
El primer capítol introdueix una perspectiva de l'aprenentatge automàtic on les dades s'entén com una xarxa d'entitats connectades. Aquesta estratègia es centra en les relacions entre entitats per aprendre, en contrast amb les solucions tradicionals basades en instancies i els seus atributs. Discutim sobre la importància d'aquesta perspectiva connectivista (a la que ens referim com mineria de grafs) en el context actual on grans conjunts de dades basats en xarxes estan apareixent. El capítol finalitza amb la presentació del problema de Predicció d'Arestes (PA), junt amb una primera anàlisi de les seves limitacions actuals. El segon capítol presenta les primeres contribucions a la mineria de grafs, introduint problemes típicament solucionats mitjançant aquest paradigma. El capítol es centra en l'estat de l'art de PA. Presenta tres solucions diferents per al problema i argumenta la importància del més computacionalment escalable: els algoritmes basats en similitud. Categoritza aquests en tres tipus, i per als més escalables d'aquests, els algoritmes locals, s'identifica i es descriu formalment les propostes més competitives d'acord amb la bibliografia. El tercer capítol analitza el problema de PA, inicialment com a problema de classificació binari. Una llista de propietats de grafs són discutides en el context de la PA, com la direccionalitat o els pesos. Segueix una anàlisi del cost computacional en temps com en espai, dels algorismes basats en similitud. El capítol finalitza amb un estudi del desbalanceig de classes, freqüent en la PA. Al capítol quatre es presenta un nou algorisme basat en similitud per la PA. El capítol elabora sobre la importància de les jerarquies a la representació del coneixement a través de grafs dirigits. Varies modificacions es proposen per al nou algorisme. Aquest capítol també inclou una modificació sobre els actuals algorismes de similitud per a grafs no dirigits, per adaptar-los per a grafs dirigits. Les metodologies d'avaluació de la PA s'analitzen al cinquè capítol. Comença amb una discussió sobre els problemes que suposa avaluar un context amb un gran desbalanceig de classes, identificant les metodologies apropiades per aquests casos. Es proposa una modificació sobre el mètode més apropiat actualment disponible, per tal de centrar-se en les prediccions rellevants. Segueix una discussió sobre l'estimació fidedigna de la precisió dels predictors. El sisè capítol descriu els grafs usats per avaluar els algorismes, així com la metodologia usada per transformar-los en grafs dirigits. Les raons per triar aquest conjunt de grafs són exposades, posant especial interès al cas dels grafs web i a la seva ben coneguda relació amb les jerarquies. Les propietats més bàsiques de cada graf resultant són descrites. Els tests efectuats es mostren al capítol setè. Els tres algorismes actuals de PA més competitius són comparats amb ells mateixos i amb la versió per a grafs dirigits definida anteriorment. L'algorisme proposat anteriorment i les seves modificacions també són avaluats. El problema de la PA en grafs web es considera per separat, avaluant sis grafs web diferents. El capítol acaba amb una discussió sobre les limitacions de les avaluacions formals, mostrant exemples de prediccions obtingudes. El vuitè capítol inclou els aspectes computacionals de la tesi. Comença amb una discussió sobre la importància de la gestió de memòria per a la definició del cost computacional dels algorismes de PA. Inclou una proposta sobre com reduir aquest cost mitjançant una reducció en la precisió. Segueix una secció centrada en la paral·lelització del codi, que inclou dues implementacions diferents, una en un model de programació específic per grafs (Pregel) i una amb un model de programació paral·lela genèric (OpenMP). El capítol finalitza amb una especificació dels recursos computacionals usats per als tests realitzats. Les conclusions de la tesi es presenten al capítol novè, i les línies de treball futur al desè
APA, Harvard, Vancouver, ISO, and other styles
8

Koshan, Jeffrey W. "Finite covers of homogeneous directed graphs." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape9/PQDD_0026/NQ51884.pdf.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Kelner, Judith. "Using directed graphs for software visualisation." Thesis, University of Kent, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.334043.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Naia, dos Santos Tassio. "Large structures in dense directed graphs." Thesis, University of Birmingham, 2018. http://etheses.bham.ac.uk//id/eprint/8658/.

Full text
Abstract:
We answer questions in extremal combinatorics, for directed graphs. Specifically, we investigate which large tree-like directed graphs are contained in all dense directed graphs of large order. More precisely, let T be an oriented tree of order n; among others, we establish the following results. (1) We obtain a sufficient condition which ensures every tournament of order n contains T, and show that almost every tree possesses this property. (2) We prove that for all positive C, ɛ and sufficiently large n, every tournament of order (1+ɛ)n contains T if Δ(T)≤(log n)^C. (3) We prove that for all positive Δ, ɛ and sufficiently large n, every directed graph G of order n and minimum semidegree (1/2+ɛ)n contains T if Δ(T)≤Δ. (4) We obtain a sufficient condition which ensures that every directed graph G of order n with minimum semidegree at least (1/2+ɛ)n contains T, and show that almost every tree possesses this property. (5) We extend our method in (4) to a class of tree-like spanning graphs which includes all orientations of Hamilton cycles and large subdivisions of any graph. Result (1) confirms a conjecture of Bender and Wormald and settles a conjecture of Havet and Thomassé for almost every tree; (2) strengthens a result of Kühn, Mycroft and Osthus; (3) is a directed graph analogue of a classical result of Komlós, Sárközy and Szemerédi and is implied by (4) and (5) is of independent interest.
APA, Harvard, Vancouver, ISO, and other styles
11

Chen, Siqi. "Community Detection in Large Directed Graphs." University of Cincinnati / OhioLINK, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1592170504620766.

Full text
APA, Harvard, Vancouver, ISO, and other styles
12

Chaturvedi, Mmanu. "A Parametric Classification of Directed Acyclic Graphs." Thesis, Colorado State University, 2017. http://pqdtopen.proquest.com/#viewpdf?dispub=10599253.

Full text
Abstract:

We consider four NP-hard optimization problems on directed acyclic graphs (DAGs), namely, max clique, min coloring, max independent set and min clique cover. It is well-known that these four problems can be solved in polynomial time on transitive DAGs. It is also known that there can be no polynomial O(n1–ϵ)-approximation algorithms for these problems on the general class of DAGs unless P = NP. We propose a new parameter, β, as a measure of departure from transitivity for DAGs. We define β to be the number of vertices in a longest path in a DAG such that there is no edge from the first to the last vertex of the path, and 2 if the graph is transitive. Different values of β define a hierarchy of classes of DAGs, starting with the class of transitive DAGs. We give a polynomial time algorithm for finding a max clique when β is bounded by a fixed constant. The algorithm is exponential in β, but we also give a polynomial β-approximation algorithm. We prove that the other three decision problems are NP-hard even for β ≥ 4 and give polynomial algorithms with approximation bounds of β or better in each case. Furthermore, generalizing the definition of quasi-transitivity introduced by Ghouilà-Houri, we define β-quasi-transitivity and prove a more generalized version their theorem relating quasi-transitive orientation and transitive orientation.

APA, Harvard, Vancouver, ISO, and other styles
13

Coleman, Jason. "Thesis shmesis representing reduplication with directed graphs /." Diss., Connect to the thesis, 2004. http://hdl.handle.net/10066/1482.

Full text
APA, Harvard, Vancouver, ISO, and other styles
14

Denev, A. "Financial networks as directed cyclic graphs – draft." Thesis, Українська академія банківської справи Національного банку України, 2014. http://essuir.sumdu.edu.ua/handle/123456789/59293.

Full text
APA, Harvard, Vancouver, ISO, and other styles
15

Jahanbakht, Nafiseh, and University of Lethbridge Faculty of Arts and Science. "Energy of graphs and digraphs." Thesis, Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2010, 2010. http://hdl.handle.net/10133/2489.

Full text
Abstract:
The energy of a graph is the sum of the absolute values of the eigenvalues of its adjacency matrix. The concept is related to the energy of a class of molecules in chemistry and was first brought to mathematics by Gutman in 1978 ([8]). In this thesis, we do a comprehensive study on the energy of graphs and digraphs. In Chapter 3, we review some existing upper and lower bounds for the energy of a graph. We come up with some new results in this chapter. A graph with n vertices is hyper-energetic if its energy is greater than 2n−2. Some classes of graphs are proved to be hyper-energetic. We find a new class of hyper-energetic graphs which is introduced and proved to be hyper-energetic in Section 3.3. The energy of a digraph is the sum of the absolute values of the real part of the eigenvalues of its adjacency matrix. In Chapter 4, we study the energy of digraphs in a way that Pe˜na and Rada in [19] have defined. Some known upper and lower bounds for the energy of digraphs are reviewed. In Section 4.5, we bring examples of some classes of digraphs in which we find their energy. Keywords. Energy of a graph, hyper-energetic graph, energy of a digraph.
vii, 80 leaves ; 29 cm
APA, Harvard, Vancouver, ISO, and other styles
16

JAIN, RACHANA. "IMPROVED TECHNIQUES IN GRAPH DRAWING USING FORCE DIRECTED METHODS FOR MODERATE SIZE GRAPHS." University of Cincinnati / OhioLINK, 2004. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1081543392.

Full text
APA, Harvard, Vancouver, ISO, and other styles
17

Slade, Michael L. "A layout algorithm for hierarchical graphs with constraints /." Online version of thesis, 1994. http://hdl.handle.net/1850/11724.

Full text
APA, Harvard, Vancouver, ISO, and other styles
18

Reynolds, Jason. "A hierarchical layout algorithm for drawing directed graphs." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp04/mq20694.pdf.

Full text
APA, Harvard, Vancouver, ISO, and other styles
19

d'Oliveira, Kyle. "Link scheduling directed graphs using undirected edge colours." Thesis, University of British Columbia, 2012. http://hdl.handle.net/2429/42329.

Full text
Abstract:
Communication in a wireless network is typically modeled as either a directed or an undirected communication graph. Link scheduling is the problem of assigning time slots to each edge so that communication on every edge at its assigned time may occur without interference. Interference is also modeled as a graph, typically the same as the communication graph. However, interference may occur even without the desire or possibility of communication and warrants its own graph. When link scheduling directed graphs, Packet Radio Network (PRN)-colouring is used to create a link schedule. When modeled as an undirected graph, strong edge colouring is typically used to create a link schedule. Both PRN and strong edge colouring have been shown to be NP-complete. In this thesis, two new types of undirected edge colourings are analyzed: Acyclic Colour Induced (ACI) and Even Cycle Parity Colour Induced (ECPCI) edge colouring. Both ACI and ECPCI edge colouring are less restrictive than strong edge colouring in the sense that a strong edge colouring provides both an ACI and an ECPCI edge colouring; in fact, it is possible to use significantly fewer colours. Further, there is a translation that will take an ACI or an ECPCI edge colouring of an undirected graph and transform it into a directed PRN-colouring of the corresponding symmetric directed graph.These two new types of edge colourings are shown to be NP-complete. Lower bounds for ACI and ECPCI edge colouring planar graphs are analyzed. It is shown that there exists planar graphs with maximum degree Δ that require 33Δ/16 (respectively 2Δ+1) colours in an ACI (respectively ECPCI) edge colouring. Also, algorithms are given for strong, ACI, and ECPCI edge colouring that take into account a communication graph that is a subgraph of the interference graph. Using these algorithms, a link schedule using PRN-colouring on directed communication and interference graphs can be created that is an Ο(1) and Ο(\sqrt{\gamma}) approximation for planar and general graphs with genus γ≥1 respectively. The approximation algorithm given improves the best known upper bound for link scheduling planar graphs.
APA, Harvard, Vancouver, ISO, and other styles
20

Mycroft, Richard. "The regularity method in directed graphs and hypergraphs." Thesis, University of Birmingham, 2010. http://etheses.bham.ac.uk//id/eprint/1036/.

Full text
Abstract:
In recent years the regularity method has been used to tackle many embedding problems in extremal graph theory. This thesis demonstrates and develops three different techniques which can be used in conjunction with the regularity method to solve such problems. These methods enable us to prove an approximate version of the well-known Sumner’s universal tournament conjecture, first posed in 1971, which states that any tournament G on 2n − 2 vertices contains a copy of any directed tree T on n vertices. An analysis of the extremal cases then proves that Sumner’s universal tournament conjecture holds for any sufficiently large n. Our methods are also applied to the problem of obtaining hypergraph analogues of Dirac’s theorem. Indeed, we show that for any k \(\geqslant\) 3 and any 1 \(\leqslant\) \(\ell\) \(\leqslant\) k − 1 with k - \(\ell\)\(\nmid\)k, any k-uniform hypergraph on n vertices with minimum degree at least \(\frac{n}{\lceil k / (k - \ell) \rceil (k - \ell)}\) + o(n) contains a Hamilton \(\ell\)-cycle. This result confirms a conjecture of Han and Schacht, and is best possible up to the o(n) error term. Together with results of Rodl, Rucinski and Szemeredi, this result asymptotically determines the minimum degree which forces an \(\ell\)-cycle for any \(\ell\) with 1 \(\leqslant\)\(\ell\)\(\leqslant\) k − 1.
APA, Harvard, Vancouver, ISO, and other styles
21

Amundsson, Karl. "Approximate Bayesian Learning of Partition Directed Acyclic Graphs." Thesis, KTH, Matematisk statistik, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-192853.

Full text
Abstract:
Partition directed acyclic graphs (PDAGs) is a model whereby the conditional probability tables (CPTs) are partitioned into parts with equal probability. In this way, the number of parameters that need to be learned can be significantly reduced so that some problems become more computationally feasible. PDAGs have been shown to be connected to labeled DAGs (LDAGs) and the connection is summarized here. Furthermore, a clustering algorithm is compared to an exact algorithm for determining a PDAG. To evaluate the algorithm, we use it on simulated data where the expected result is known.
Partitionerade riktade acykliska grafer (engelska: PDAGs) är en modell där tabeller över betingade sannolikheter partitioneras i delar med lika sannolikhet. Detta gör att antalet parametrar som ska bestämmas kan reduceras, vilket i sin tur gör problemet beräkningsmässigt enklare. Ett känt samband mellan PDAGs och betecknade riktade acykliska grafer (engelska: LDAGs) sammanfattas här. Sedan jämförs en klustringsalgoritm med en algoritm som exakt bestämmer en PDAG. Klustringsalgoritmens pålitlighet kollas genom att använda den på simulerad data där det förväntade resultatet är känt.
APA, Harvard, Vancouver, ISO, and other styles
22

Cederquist, Aaron. "Frequent Pattern Mining among Weighted and Directed Graphs." Case Western Reserve University School of Graduate Studies / OhioLINK, 2009. http://rave.ohiolink.edu/etdc/view?acc_num=case1228328123.

Full text
APA, Harvard, Vancouver, ISO, and other styles
23

Poole, Daniel James. "A Study of Random Hypergraphs and Directed Graphs." The Ohio State University, 2014. http://rave.ohiolink.edu/etdc/view?acc_num=osu1397222674.

Full text
APA, Harvard, Vancouver, ISO, and other styles
24

Couch, Marshall. "Effects of Curved Lines on Force-Directed Graphs." Digital Commons @ East Tennessee State University, 2013. https://dc.etsu.edu/honors/64.

Full text
Abstract:
The most common methods for simplifying force-directed graphs are edge-bundling and edge routing. Both of these methods can be done with curved, rather than straight, lines which some researchers have argued. Curved lines have been offered as a solution for clarifying edge resolution. Curved lines were originally thought to be more aesthetically pleasing. 32 computer science students were surveyed and asked questions about straight and curved line graphs. Research conducted by Xu et al. and this study suggests that curved lines make a graph more difficult to understand and slower to read. Research also suggests that curved lines are no more aesthetically pleasing than straight lines. Situations may exist where curved lines are beneficial to a graph’s readability, but it is unclear due to uncontrolled variables in this study. Further study could reveal circumstances when curved lines would be beneficial.
APA, Harvard, Vancouver, ISO, and other styles
25

Hartman, Gregory Neil. "Graphs and Noncommutative Koszul Algebras." Diss., Virginia Tech, 2002. http://hdl.handle.net/10919/27156.

Full text
Abstract:
A new connection between combinatorics and noncommutative algebra is established by relating a certain class of directed graphs to noncommutative Koszul algebras. The directed graphs in this class are called full graphs and are defined by a set of criteria on the edges. The structural properties of full graphs are studied as they relate to the edge criteria. A method is introduced for generating a Koszul algebra Lambda from a full graph G. The properties of Lambda are examined as they relate to the structure of G, with special attention being given to the construction of a projective resolution of certain semisimple Lambda-modules based on the structural properties of G. The characteristics of the Koszul algebra Lambda that is derived from the product of two full graphs G' and G' are studied as they relate to the properties of the Koszul algebras Lambda' and Lambda' derived from G' and G'.
Ph. D.
APA, Harvard, Vancouver, ISO, and other styles
26

Li, Yuemeng. "Spectral Analysis of Directed Graphs using Matrix Perturbation Theory." Thesis, The University of North Carolina at Charlotte, 2017. http://pqdtopen.proquest.com/#viewpdf?dispub=10618933.

Full text
Abstract:

The spectral space of the adjacency matrix contains important structural information of a given network (graph), where such information can be leveraged in developing a variety of algorithms in applications such as graph partition, structural hierarchy discovery, and anomaly detection. Although many prominent works have laid the foundation for studying the graph spectra, it is still challenging to analyze the spectral space properties for directed graphs due to possible complex valued decompositions. Matrix factorization techniques such as Laplacian and normalized Laplacian have been widely adopted to study the associated spectral spaces, but network structural properties may not be well preserved in those spectral spaces due to transformations.

In this dissertation work, we explore the adjacency eigenspace of directed graphs using matrix perturbation theory and examine the relationships between graph structures and the spectral projection patterns. We study how to detect dominant structures such as clusters or anomalous nodes by establishing a connection between the connectivity of nodes and the geometric relationships in the adjacency eigenspace. We leverage selected key results from perturbation theory, linear algebra and graph theory as our tools to derive theoretical results that help to elaborate observed graph spectral projection patterns. In order to validate our theoretical results, novel algorithms including spectral clustering for both signed and unsigned networks, asymmetry analysis for network dominance, and anomaly analysis for streaming network data are developed and tested on both synthetic and real datasets. The empirical evaluation results suggest that our algorithms performs better when compared with existing state-of-the-art methods.

APA, Harvard, Vancouver, ISO, and other styles
27

Choudhry, Arjun. "Narrative Generation to Support Causal Exploration of Directed Graphs." Thesis, Virginia Tech, 2020. http://hdl.handle.net/10919/98670.

Full text
Abstract:
Causal graphs are a useful notation to represent the interplay between the actors as well as the polarity and strength of the relationship that they share. They are used extensively in educational, professional, and industrial contexts to simulate different scenarios, validate behavioral aspects, visualize the connections between different processes, and explore the adversarial effects of changing certain nodes. However, as the size of the causal graphs increase, interpreting them also becomes increasingly tougher. In such cases, new analytical tools are required to enhance the user's comprehension of the graph, both in terms of correctness and speed. To this purpose, this thesis introduces 1) a system that allows for causal exploration of directed graphs, while enabling the user to see the effect of interventions on the target nodes, 2) the use of natural language generation techniques to create a coherent passage explaining the propagation effects, and 3) results of an expert user study validating the efficacy of the narratives in enhancing the user's understanding of the causal graphs. In overall, the system aims to enhance user experience and promote further causal exploration.
Master of Science
Narrative generation is the art of creating coherent snippets of text that cumulatively describe a succession of events, played across a period of time. These goals of narrative generation are also shared by causal graphs – models that encapsulate inferences between the nodes through the strength and polarity of the connecting edges. Causal graphs are an useful mechanism to visualize changes propagating amongst nodes in the system. However, as the graph starts addressing real-world actors and their interactions, it becomes increasingly difficult to understand causal inferences between distant nodes, especially if the graph is cyclic. Moreover, if the value of more than a single node is altered and the cumulative effect of the change is to be perceived on a set of target nodes, it becomes extremely difficult to the human eye. This thesis attempts to alleviate this problem by generating dynamic narratives detailing the effect of one or more interventions on one or more target nodes, incorporating time-series analysis, Wikification, and spike detection. Moreover, the narrative enhances the user's understanding of the change propagation occurring in the system. The efficacy of the narrative was further corroborated by the results of user studies, which concluded that the presence of the narrative aids the user's confidence level, correctness, and speed while exploring the causal network.
APA, Harvard, Vancouver, ISO, and other styles
28

Bosi, Gianluca <1991&gt. "Simple random walks on some partially directed planar graphs." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2019. http://amsdottorato.unibo.it/8914/1/bosi_gianluca_tesi.pdf.

Full text
Abstract:
In this thesis we analyze the recurrence behavior of simple random walks on some classes of directed planar graphs. Our first model is a version of the honeycomb lattice, where the horizontal edges are randomly oriented according to families of random variables: depending on their distribution, we prove a.s. transience in some cases, and a.s. recurrence in other ones. Our results extend those obtained by Campanino and Petritis (’03 and ’14) for partially oriented square grid lattices. Furthermore, we consider two directed square grid lattices on which, because of the direction imposed by the oriented edges, the simple random walk is bound to revolve clockwise: we prove recurrence for one of the graphs, solving a conjecture of Menshikov et al. (’17), and we give a new proof of transience for the other one.
APA, Harvard, Vancouver, ISO, and other styles
29

ARTARIA, ANDREA. "Objective Bayesian Analysis for Differential Gaussian Directed Acyclic Graphs." Doctoral thesis, Università degli Studi di Milano-Bicocca, 2014. http://hdl.handle.net/10281/55327.

Full text
Abstract:
Often we are confronted with heterogeneous multivariate data, i.e., data coming from several categories, and the interest may center on the differential structure of stochastic dependence among the variables between the groups. The focus in this work is on the two groups problem and is faced modeling the system through a Gaussian directed acyclic graph (DAG) couple linked in a fashion to obtain a joint estimation in order to exploit, whenever they exist, similarities between the graphs. The model can be viewed as a set of separate regressions and the proposal consists in assigning a non-local prior to the regression coefficients with the objective of enforcing stronger sparsity constraints on model selection. The model selection is based on Moment Fractional Bayes Factor, and is performed through a stochastic search algorithm over the space of DAG models.
APA, Harvard, Vancouver, ISO, and other styles
30

Prego, Lilach. "Algorithm for directed graph clustering, based on edge weights and the implementation on web graphs /." [S.l.] : [s.n.], 2005. http://lib.haifa.ac.il/theses/general/001344252.pdf.

Full text
APA, Harvard, Vancouver, ISO, and other styles
31

Mihalisin, James Edward. "Polytopal digraphs and non-polytopal facet graphs /." Thesis, Connect to this title online; UW restricted, 2001. http://hdl.handle.net/1773/5760.

Full text
APA, Harvard, Vancouver, ISO, and other styles
32

Boore, Graeme C. "Directed graph iterated function systems." Thesis, University of St Andrews, 2011. http://hdl.handle.net/10023/2109.

Full text
Abstract:
This thesis concerns an active research area within fractal geometry. In the first part, in Chapters 2 and 3, for directed graph iterated function systems (IFSs) defined on ℝ, we prove that a class of 2-vertex directed graph IFSs have attractors that cannot be the attractors of standard (1-vertex directed graph) IFSs, with or without separation conditions. We also calculate their exact Hausdorff measure. Thus we are able to identify a new class of attractors for which the exact Hausdorff measure is known. We give a constructive algorithm for calculating the set of gap lengths of any attractor as a finite union of cosets of finitely generated semigroups of positive real numbers. The generators of these semigroups are contracting similarity ratios of simple cycles in the directed graph. The algorithm works for any IFS defined on ℝ with no limit on the number of vertices in the directed graph, provided a separation condition holds. The second part, in Chapter 4, applies to directed graph IFSs defined on ℝⁿ . We obtain an explicit calculable value for the power law behaviour as r → 0⁺ , of the qth packing moment of μ[subscript(u)], the self-similar measure at a vertex u, for the non-lattice case, with a corresponding limit for the lattice case. We do this (i) for any q ∈ ℝ if the strong separation condition holds, (ii) for q ≥ 0 if the weaker open set condition holds and a specified non-negative matrix associated with the system is irreducible. In the non-lattice case this enables the rate of convergence of the packing L[superscript(q)]-spectrum of μ[subscript(u)] to be determined. We also show, for (ii) but allowing q ∈ ℝ, that the upper multifractal q box-dimension with respect to μ[subscript(u)], of the set consisting of all the intersections of the components of F[subscript(u)], is strictly less than the multifractal q Hausdorff dimension with respect to μ[subscript(u)] of F[subscript(u)].
APA, Harvard, Vancouver, ISO, and other styles
33

Walker, DayVon L. "Power Graphs of Quasigroups." Scholar Commons, 2019. https://scholarcommons.usf.edu/etd/7984.

Full text
Abstract:
We investigate power graphs of quasigroups. The power graph of a quasigroup takes the elements of the quasigroup as its vertices, and there is an edge from one element to a second distinct element when the second is a left power of the first. We first compute the power graphs of small quasigroups (up to four elements). Next we describe quasigroups whose power graphs are directed paths, directed cycles, in-stars, out-stars, and empty. We do so by specifying partial Cayley tables, which cannot always be completed in small examples. We then consider sinks in the power graph of a quasigroup, as subquasigroups give rise to sinks. We show that certain structures cannot occur as sinks in the power graph of a quasigroup. More generally, we show that certain highly connected substructures must have edges leading out of the substructure. We briefly comment on power graphs of Bol loops.
APA, Harvard, Vancouver, ISO, and other styles
34

Gaslowitz, Joshua Z. "Chip Firing Games and Riemann-Roch Properties for Directed Graphs." Scholarship @ Claremont, 2013. http://scholarship.claremont.edu/hmc_theses/42.

Full text
Abstract:
The following presents a brief introduction to tropical geometry, especially tropical curves, and explains a connection to graph theory. We also give a brief summary of the Riemann-Roch property for graphs, established by Baker and Norine (2007), as well as the tools used in their proof. Various generalizations are described, including a more thorough description of the extension to strongly connected directed graphs by Asadi and Backman (2011). Building from their constructions, an algorithm to determine if a directed graph has Row Riemann-Roch Property is given and thoroughly explained.
APA, Harvard, Vancouver, ISO, and other styles
35

Sahai, Amit 1974. "The power of a pebble : exploring and mapping directed graphs." Thesis, Massachusetts Institute of Technology, 1998. http://hdl.handle.net/1721.1/47437.

Full text
APA, Harvard, Vancouver, ISO, and other styles
36

Gabrysch, Katja. "On Directed Random Graphs and Greedy Walks on Point Processes." Doctoral thesis, Uppsala universitet, Analys och sannolikhetsteori, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-305859.

Full text
Abstract:
This thesis consists of an introduction and five papers, of which two contribute to the theory of directed random graphs and three to the theory of greedy walks on point processes.           We consider a directed random graph on a partially ordered vertex set, with an edge between any two comparable vertices present with probability p, independently of all other edges, and each edge is directed from the vertex with smaller label to the vertex with larger label. In Paper I we consider a directed random graph on ℤ2 with the vertices ordered according to the product order and we show that the limiting distribution of the centered and rescaled length of the longest path from (0,0) to (n, [na] ), a<3/14, is the Tracy-Widom distribution. In Paper II we show that, under a suitable rescaling, the closure of vertex 0 of a directed random graph on ℤ with edge probability n−1 converges in distribution to the Poisson-weighted infinite tree. Moreover, we derive limit theorems for the length of the longest path of the Poisson-weighted infinite tree.           The greedy walk is a deterministic walk on a point process that always moves from its current position to the nearest not yet visited point. Since the greedy walk on a homogeneous Poisson process on the real line, starting from 0, almost surely does not visit all points, in Paper III we find the distribution of the number of visited points on the negative half-line and the distribution of the index at which the walk achieves its minimum. In Paper IV we place homogeneous Poisson processes first on two intersecting lines and then on two parallel lines and we study whether the greedy walk visits all points of the processes. In Paper V we consider the greedy walk on an inhomogeneous Poisson process on the real line and we determine sufficient and necessary conditions on the mean measure of the process for the walk to visit all points.
APA, Harvard, Vancouver, ISO, and other styles
37

Brückner, Guido [Verfasser], and D. [Akademischer Betreuer] Wagner. "Planarity Variants for Directed Graphs / Guido Brückner ; Betreuer: D. Wagner." Karlsruhe : KIT-Bibliothek, 2021. http://d-nb.info/1238148018/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
38

Lin, Lequan. "A Magnetic Framelet-Based Convolutional Neural Network for Directed Graphs." Thesis, The University of Sydney Business School, Discipline of Business Analytics, 2023. https://hdl.handle.net/2123/29941.

Full text
Abstract:
Recent years have witnessed the surging popularity among studies on directed graphs (digraphs) and digraph neural networks. With the unique capability of encoding directional relationships, digraphs have shown their superiority in modelling many real-life applications, such as citation analysis and website hyperlinks. Spectral Graph Convolutional Neural Networks (spectral GCNNs), a powerful tool for processing and analyzing undirected graph data, have been recently introduced to digraphs. Although spectral GCNNs typically apply frequency filtering via Fourier transform to obtain representations with selective information, research shows that model performance can be enhanced by framelet transform-based filtering. However, the massive majority of such research only considers spectral GCNNs for undirected graphs. In this thesis, we introduce Framelet-MagNet, a magnetic framelet-based spectral GCNN for digraphs. The model adopts magnetic framelet transform which decomposes the input digraph data to low-pass and high-pass frequency components in the spectral domain, forming a more sophisticated digraph representation for filtering. Digraph framelets are constructed with the complex-valued magnetic Laplacian, simultaneously leading to signal processing in both real and complex domains. To our best knowledge, this approach is the first attempt to conduct framelet-based convolution on digraph data in both real and complex domains. We empirically validate the predictive power of Framelet-MagNet via various tasks, including node classification, link prediction, and denoising. Besides, we show through experiment results that Framelet-MagNet can outperform the state-of-the-art approaches across several benchmark datasets.
APA, Harvard, Vancouver, ISO, and other styles
39

Araújo, Paulo Ventura. "Almost flow equivalence and the loop structure of directed graphs." Thesis, University of Warwick, 1992. http://wrap.warwick.ac.uk/110604/.

Full text
Abstract:
We investigate the problem of almost flow equivalence for sub-shifts of finite type (SFT). The problem is to decide when two suspension flows of irreducible SFT are almost everywhere one to one factors of the same suspension flow, a problem that was solved by Mike Boyle. We obtain generalizations of Boyle’s result by considering the similar problems for Markov shifts and for SFT with finite group actions. We also undertake an analysis of the loop structure of directed graphs, and we reduce some problems concerning loops to the study of the loop diagram, which is a convenient form of representing the simple cycles of a given directed graph.
APA, Harvard, Vancouver, ISO, and other styles
40

Tamburini, Caterina. "The isomorphism problem for directed acyclic graphs: an application to multivector fields." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2018. http://amslaurea.unibo.it/15793/.

Full text
Abstract:
This thesis is based on a project developed by a group of researchers at the Faculty of Mathematics and Computer Science at the Jagiellonian University of Krakow. They study sampled dynamics using combinatorial multivector fields. Applying a decomposition into strongly connected components, it is possible to create a directed acyclic graph, called Morse graph, which is a description of the multivector field's global dynamics. Therefore the purpose of this thesis is to compare directed acyclic graphs. In the first chapter we describe the creation process of a Morse graph and an algorithm to study the graph isomorphism problem. The second chapter is dedicated to our personal work, so we describe four Python tests we developed to establish whether two directed acyclic graphs are definitely not isomorphic. In the third chapter we sum up many examples. The last chapter aims to present a possible way for the future work, that is to treat a combinatorial multivector filed as a finite topological space.
APA, Harvard, Vancouver, ISO, and other styles
41

Sariaydin, Ayse. "Computation And Analysis Of Spectra Of Large Networks With Directed Graphs." Master's thesis, METU, 2010. http://etd.lib.metu.edu.tr/upload/12612249/index.pdf.

Full text
Abstract:
Analysis of large networks in biology, science, technology and social systems have become very popular recently. These networks are mathematically represented as graphs. The task is then to extract relevant qualitative information about the empirical networks from the analysis of these graphs. It was found that a graph can be conveniently represented by the spectrum of a suitable difference operator, the normalized graph Laplacian, which underlies diffusions and random walks on graphs. When applied to large networks, this requires computation of the spectrum of large matrices. The normalized Laplacian matrices representing large networks are usually sparse and unstructured. The thesis consists in a systematic evaluation of the available eigenvalue solvers for nonsymmetric large normalized Laplacian matrices describing directed graphs of empirical networks. The methods include several Krylov subspace algorithms like implicitly restarted Arnoldi method, Krylov-Schur method and Jacobi-Davidson methods which are freely available as standard packages written in MATLAB or SLEPc, in the library written C++. The normalized graph Laplacian as employed here is normalized such that its spectrum is confined to the range [0, 2]. The eigenvalue distribution plays an important role in network analysis. The numerical task is then to determine the whole spectrum with appropriate eigenvalue solvers. A comparison of the existing eigenvalue solvers is done with Paley digraphs with known eigenvalues and for citation networks in sizes 400, 1100 and 4500 by computing the residuals.
APA, Harvard, Vancouver, ISO, and other styles
42

Rafiey-Hafshejani, Arash. "Extremal and optimization problems on dense directed and edge-coloured graphs." Thesis, Royal Holloway, University of London, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.435465.

Full text
APA, Harvard, Vancouver, ISO, and other styles
43

Takagi, Kazuyoshi. "Design and Analysis of VLSI Circuits Based on Directed Acyclic Graphs." Kyoto University, 1999. http://hdl.handle.net/2433/157068.

Full text
Abstract:
本文データは平成22年度国立国会図書館の学位論文(博士)のデジタル化実施により作成された画像ファイルを基にpdf変換したものである
Kyoto University (京都大学)
0048
新制・論文博士
博士(工学)
乙第10127号
論工博第3442号
新制||工||1151(附属図書館)
UT51-99-G604
(主査)教授 岩間 一雄, 教授 上林 彌彦, 教授 富田 眞治
学位規則第4条第2項該当
APA, Harvard, Vancouver, ISO, and other styles
44

Mantrach, Amin. "Novel measures on directed graphs and applications to large-scale within-network classification." Doctoral thesis, Universite Libre de Bruxelles, 2010. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210033.

Full text
Abstract:
Ces dernières années, les réseaux sont devenus une source importante d’informations dans différents domaines aussi variés que les sciences sociales, la physique ou les mathématiques. De plus, la taille de ces réseaux n’a cessé de grandir de manière conséquente. Ce constat a vu émerger de nouveaux défis, comme le besoin de mesures précises et intuitives pour caractériser et analyser ces réseaux de grandes tailles en un temps raisonnable.

La première partie de cette thèse introduit une nouvelle mesure de similarité entre deux noeuds d’un réseau dirigé et pondéré :la covariance “sum-over-paths”. Celle-ci a une interprétation claire et précise :en dénombrant tous les chemins possibles deux noeuds sont considérés comme fortement corrélés s’ils apparaissent souvent sur un même chemin – de préférence court. Cette mesure dépend d’une distribution de probabilités, définie sur l’ensemble infini dénombrable des chemins dans le graphe, obtenue en minimisant l'espérance du coût total entre toutes les paires de noeuds du graphe sachant que l'entropie relative totale injectée dans le réseau est fixée à priori. Le paramètre d’entropie permet de biaiser la distribution de probabilité sur un large spectre :allant de marches aléatoires naturelles où tous les chemins sont équiprobables à des marches biaisées en faveur des plus courts chemins. Cette mesure est alors appliquée à des problèmes de classification semi-supervisée sur des réseaux de taille moyennes et comparée à l’état de l’art.

La seconde partie de la thèse introduit trois nouveaux algorithmes de classification de noeuds en sein d’un large réseau dont les noeuds sont partiellement étiquetés. Ces algorithmes ont un temps de calcul linéaire en le nombre de noeuds, de classes et d’itérations, et peuvent dés lors être appliqués sur de larges réseaux. Ceux-ci ont obtenus des résultats compétitifs en comparaison à l’état de l’art sur le large réseaux de citations de brevets américains et sur huit autres jeux de données. De plus, durant la thèse, nous avons collecté un nouveau jeu de données, déjà mentionné :le réseau de citations de brevets américains. Ce jeu de données est maintenant disponible pour la communauté pour la réalisation de tests comparatifs.

La partie finale de cette thèse concerne la combinaison d’un graphe de citations avec les informations présentes sur ses noeuds. De manière empirique, nous avons montré que des données basées sur des citations fournissent de meilleurs résultats de classification que des données basées sur des contenus textuels. Toujours de manière empirique, nous avons également montré que combiner les différentes sources d’informations (contenu et citations) doit être considéré lors d’une tâche de classification de textes. Par exemple, lorsqu’il s’agit de catégoriser des articles de revues, s’aider d’un graphe de citations extrait au préalable peut améliorer considérablement les performances. Par contre, dans un autre contexte, quand il s’agit de directement classer les noeuds du réseau de citations, s’aider des informations présentes sur les noeuds n’améliora pas nécessairement les performances.

La théorie, les algorithmes et les applications présentés dans cette thèse fournissent des perspectives intéressantes dans différents domaines.

In recent years, networks have become a major data source in various fields ranging from social sciences to mathematical and physical sciences. Moreover, the size of available networks has grow substantially as well. This has brought with it a number of new challenges, like the need for precise and intuitive measures to characterize and analyze large scale networks in a reasonable time.

The first part of this thesis introduces a novel measure between two nodes of a weighted directed graph: The sum-over-paths covariance. It has a clear and intuitive interpretation: two nodes are considered as highly correlated if they often co-occur on the same -- preferably short -- paths. This measure depends on a probability distribution over the (usually infinite) countable set of paths through the graph which is obtained by minimizing the total expected cost between all pairs of nodes while fixing the total relative entropy spread in the graph. The entropy parameter allows to bias the probability distribution over a wide spectrum: going from natural random walks (where all paths are equiprobable) to walks biased towards shortest-paths. This measure is then applied to semi-supervised classification problems on medium-size networks and compared to state-of-the-art techniques.

The second part introduces three novel algorithms for within-network classification in large-scale networks, i.e. classification of nodes in partially labeled graphs. The algorithms have a linear computing time in the number of edges, classes and steps and hence can be applied to large scale networks. They obtained competitive results in comparison to state-of-the-art technics on the large scale U.S.~patents citation network and on eight other data sets. Furthermore, during the thesis, we collected a novel benchmark data set: the U.S.~patents citation network. This data set is now available to the community for benchmarks purposes.

The final part of the thesis concerns the combination of a citation graph with information on its nodes. We show that citation-based data provide better results for classification than content-based data. We also show empirically that combining both sources of information (content-based and citation-based) should be considered when facing a text categorization problem. For instance, while classifying journal papers, considering to extract an external citation graph may considerably boost the performance. However, in another context, when we have to directly classify the network citation nodes, then the help of features on nodes will not improve the results.

The theory, algorithms and applications presented in this thesis provide interesting perspectives in various fields.


Doctorat en Sciences
info:eu-repo/semantics/nonPublished

APA, Harvard, Vancouver, ISO, and other styles
45

Heuer, Karl [Verfasser], and Reinhard [Akademischer Betreuer] Diestel. "Connectivity in directed and undirected infinite graphs / Karl Heuer ; Betreuer: Reinhard Diestel." Hamburg : Staats- und Universitätsbibliothek Hamburg, 2018. http://d-nb.info/1169358349/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
46

Emms, Josephine. "Amalgamation classes of directed graphs in model theory and infinite permutation groups." Thesis, University of East Anglia, 2012. https://ueaeprints.uea.ac.uk/39034/.

Full text
APA, Harvard, Vancouver, ISO, and other styles
47

Chieregato, Federico. "Modelling task execution time in Directed Acyclic Graphs for efficient distributed management." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2022.

Find full text
Abstract:
In this thesis, has been shown a framework that predicts the execution time of tasks in Directed Acyclic Graphs (DAG), each task is the smallest unit of work that executes a function over a set of inputs and in this scenario represents a vertex in a DAG. This thesis includes an implementation for extracting profiling information from Apache Spark, as well, an evaluation of the framework for the Spark decision support benchmark TPC-DS and an in-house and completely different DAG runtime system for real-world DAGS, involving computational quantum chemistry applications. Speeding up the execution in Spark or other workflows is an important problem for many real-time applications; since it is impractical to generate a predictive model that considers the actual values of the inputs to tasks, has been explored the use of Surrogates as the number of parents and the mean parent duration of a task. For this reason, this solution takes the name of PRODIGIOUS, Performance modelling of DAGs via surrogate features. Since the duration of the tasks is a float value, have been studied different regression algorithms, tuning the Hyperparameters through GridSearchCV. The main objective of PRODIGIOUS concern, not only to understand if the use of surrogates instead of actual inputs is enough to predict the execution time of tasks of the same DAG type, but also if it is possible to predict the execution time of tasks of different DAG type creating so a DAG agnostic framework that could help scientist and computer engineer making more efficient their workflow. Others agnostic feature chosen were, the core for each task, the RAM of the benchmark, the data access type, and the number of executors.
APA, Harvard, Vancouver, ISO, and other styles
48

Rumyantseva, Anastasiya, and M. Zelinskaya. "System approaches to modeling of sustainable regional development applied the directed graphs." Thesis, Видавництво СумДУ, 2007. http://essuir.sumdu.edu.ua/handle/123456789/13052.

Full text
Abstract:
The mankind has got into extremely complicated and very dangerous situation at the beginning of third millennium. The most people don’t realize fully the level of threat of man’s activity and destructive consequences of this activity for environment. In fact, it has brought our planet to global ecocatastrophe. This situation has made world community look for new ways of humanity evolution. The well-known document entitled “The agenda for XXI century” accepted by International environmental conference of OUN in 1992 is one of such kind of ways. A new model of social development named sustainable development has been offered by this document. Sustainable development approach combined next ideas: harmonious interaction and unity of ecological, economic and social development. For transition to a new model of ecologically safe and energy saving development, it is necessary to seek the accordance of three above-mentioned constituents of development both at world level and at the regional level. When you are citing the document, use the following link http://essuir.sumdu.edu.ua/handle/123456789/13052
APA, Harvard, Vancouver, ISO, and other styles
49

Salmasi, Ario. "Approximation algorithms for routing and related problems on directed minor-free graphs." The Ohio State University, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=osu1562100382069027.

Full text
APA, Harvard, Vancouver, ISO, and other styles
50

Chaudhuri, Sanjay. "Using the structure of d-connecting paths as a qualitative measure of the strength of dependence /." Thesis, Connect to this title online; UW restricted, 2005. http://hdl.handle.net/1773/8948.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the bibliographies on the topic 'Directed graphs' for other source types:
Journal articles Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography