Dissertations / Theses on the topic 'Graph algorithms'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Graph algorithms.'
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.
Zhou, Hang. "Graph algorithms : network inference and planar graph optimization." Thesis, Paris, Ecole normale supérieure, 2015. http://www.theses.fr/2015ENSU0016/document.
Full textThis thesis focuses on two topics of graph algorithms. The first topic is network inference. How efficiently can we find an unknown graph using shortest path queries between its vertices? We assume that the graph has bounded degree. In the reconstruction problem, the goal is to find the graph; and in the verification problem, the goal is to check whether a given graph is correct. We provide randomized algorithms based on a Voronoi cell decomposition. Next, we analyze greedy algorithms, and show that they are near-optimal. We also study the problems on special graph classes, prove lower bounds, and study the approximate reconstruction. The second topic is optimization in planar graphs. We study two problems. In the correlation clustering problem, the input is a weighted graph, where every edge has a label of h+i or h−i, indicating whether its endpoints are in the same category or in different categories. The goal is to find a partition of the vertices into categories that tries to respect the labels. In the two-edge-connected augmentation problem, the input is a weighted graph and a subset R of edges. The goal is to produce a minimum-weight subset S of edges, such that for every edge in R, its endpoints are two-edge-connected in the union of R and S. For planar graphs, we reduce correlation clustering to two-edge-connected augmentation, and show that both problems, although they are NP-hard, have a polynomial-time approximation scheme. We build on the brick decomposition technique developed recently
Bui, Thang Nguyen. "Graph bisection algorithms." Thesis, Massachusetts Institute of Technology, 1986. http://hdl.handle.net/1721.1/77680.
Full textMICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING.
Bibliography: leaves 64-66.
by Thang Nguyen Bui.
Ph.D.
Larsson, Patrik. "Analyzing and adapting graph algorithms for large persistent graphs." Thesis, Linköping University, Department of Computer and Information Science, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-15422.
Full textIn this work, the graph database Neo4j developed by Neo Technology is presented together with some of it's functionality when it comes to accessing data as a graph. This type of data access brings the possibility to implement common graph algorithms on top of Neo4j. Examples of such algorithms are presented together with their theoretical backgrounds. These are mainly algorithms for finding shortest paths and algorithms for different graph measures such as centrality measures. The implementations that have been made are presented, as well as complexity analysis and the performance measures performed on them. The conclusions include that Neo4j is well suited for these types of implementations.
Profiti, Giuseppe <1980>. "Graph algorithms for bioinformatics." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amsdottorato.unibo.it/6914/1/profiti_giuseppe_tesi.pdf.
Full textProfiti, Giuseppe <1980>. "Graph algorithms for bioinformatics." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amsdottorato.unibo.it/6914/.
Full textBessy, Stéphane. "Some problems in graph theory and graphs algorithmic theory." Habilitation à diriger des recherches, Université Montpellier II - Sciences et Techniques du Languedoc, 2012. http://tel.archives-ouvertes.fr/tel-00806716.
Full textStewart, Anthony Graham. "Graph algorithms and complexity aspects on special graph classes." Thesis, Durham University, 2017. http://etheses.dur.ac.uk/12144/.
Full textFreeth, S. A. "Compression methods for graph algorithms." Thesis, University of Canterbury. Computer Science, 1985. http://hdl.handle.net/10092/9568.
Full textRen, Chenghui, and 任成會. "Algorithms for evolving graph analysis." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2014. http://hdl.handle.net/10722/197105.
Full textpublished_or_final_version
Computer Science
Doctoral
Doctor of Philosophy
King, David Jonathan. "Functional programming and graph algorithms." Thesis, University of Glasgow, 1996. http://theses.gla.ac.uk/1629/.
Full textHe, Dayu. "Algorithms for Graph Drawing Problems." Thesis, State University of New York at Buffalo, 2017. http://pqdtopen.proquest.com/#viewpdf?dispub=10284151.
Full textA graph G is called planar if it can be drawn on the plan such that no two distinct edges intersect each other but at common endpoints. Such drawing is called a plane embedding of G. A plane graph is a graph with a fixed embedding. A straight-line drawing G of a graph G = (V, E) is a drawing where each vertex of V is drawn as a distinct point on the plane and each edge of G is drawn as a line segment connecting two end vertices. In this thesis, we study a set of planar graph drawing problems.
First, we consider the problem of monotone drawing: A path P in a straight line drawing Γ is monotone if there exists a line l such that the orthogonal projections of the vertices of P on l appear along l in the order they appear in P. We call l a monotone line (or monotone direction) of P. G is called a monotone drawing of G if it contains at least one monotone path Puw between every pair of vertices u,w of G. Monotone drawings were recently introduced by Angelini et al. and represent a new visualization paradigm, and is also closely related to several other important graph drawing problems. As in many graph drawing problems, one of the main concerns of this research is to reduce the drawing size, which is the size of the smallest integer grid such that every graph in the graph class can be drawn in such a grid. We present two approaches for the problem of monotone drawings of trees. Our first approach show that every n-vertex tree T admits a monotone drawing on a grid of size O(n1.205) × O( n1.205) grid. Our second approach further reduces the size of drawing to 12n × 12n, which is asymptotically optimal. Both of our two drawings can be constructed in O(n) time.
We also consider monotone drawings of 3-connected plane graphs. We prove that the classical Schnyder drawing of 3-connected plane graphs is a monotone drawing on a f × f grid, which can be constructed in O(n) time.
Second, we consider the problem of orthogonal drawing. An orthogonal drawing of a plane graph G is a planar drawing of G such that each vertex of G is drawn as a point on the plane, and each edge is drawn as a sequence of horizontal and vertical line segments with no crossings. Orthogonal drawing has attracted much attention due to its various applications in circuit schematics, relationship diagrams, data flow diagrams etc. . Rahman et al. gave a necessary and sufficient condition for a plane graph G of maximum degree 3 to have an orthogonal drawing without bends. An orthogonal drawing D(G) is orthogonally convex if all faces of D(G) are orthogonally convex polygons. Chang et al. gave a necessary and sufficient condition (which strengthens the conditions in the previous result) for a plane graph G of maximum degree 3 to have an orthogonal convex drawing without bends. We further strengthen the results such that if G satisfies the same conditions as in previous papers, it not only has an orthogonally convex drawing, but also a stronger star-shaped orthogonal drawing.
Mądry, Aleksander. "From graphs to matrices, and back : new techniques for graph algorithms." Thesis, Massachusetts Institute of Technology, 2011. http://hdl.handle.net/1721.1/66014.
Full textCataloged from PDF version of thesis.
Includes bibliographical references (p. 181-192).
The growing need to deal efficiently with massive computing tasks prompts us to consider the following question: How well can we solve fundamental optimization problems if our algorithms have to run really quickly? The motivation for the research presented in this thesis stems from addressing the above question in the context of algorithmic graph theory. To pursue this direction, we develop a toolkit that combines a diverse set of modern algorithmic techniques, including sparsification, low-stretch spanning trees, the multiplicative-weights-update method, dynamic graph algorithms, fast Laplacian system solvers, and tools of spectral graph theory. Using this toolkit, we obtain improved algorithms for several basic graph problems including: -- The Maximum s-t Flow and Minimum s-t Cut Problems. We develop a new approach to computing (1 - [epsilon])-approximately maximum s-t flow and (1 + [epsilon])-approximately minimum s-t cut in undirected graphs that gives the fastest known algorithms for these tasks. These algorithms are the first ones to improve the long-standing bound of O(n3/2') running time on sparse graphs; -- Multicommodity Flow Problems. We set forth a new method of speeding up the existing approximation algorithms for multicommodity flow problems, and use it to obtain the fastest-known (1 - [epsilon])-approximation algorithms for these problems. These results improve upon the best previously known bounds by a factor of roughly [omega](m/n), and make the resulting running times essentially match the [omega](mn) "flow-decomposition barrier" that is a natural obstacle to all the existing approaches; -- " Undirected (Multi-)Cut-Based Minimization Problems. We develop a general framework for designing fast approximation algorithms for (multi-)cutbased minimization problems in undirected graphs. Applying this framework leads to the first algorithms for several fundamental graph partitioning primitives, such as the (generalized) sparsest cut problem and the balanced separator problem, that run in close to linear time while still providing polylogarithmic approximation guarantees; -- The Asymmetric Traveling Salesman Problem. We design an O( )- approximation algorithm for the classical problem of combinatorial optimization: the asymmetric traveling salesman problem. This is the first asymptotic improvement over the long-standing approximation barrier of e(log n) for this problem; -- Random Spanning Tree Generation. We improve the bound on the time needed to generate an uniform random spanning tree of an undirected graph.
by Aleksander Mądry.
Ph.D.
Nanongkai, Danupon. "Graph and geometric algorithms on distributed networks and databases." Diss., Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/41056.
Full textPajak, Dominik. "Algorithms for Deterministic Parallel Graph Exploration." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2014. http://tel.archives-ouvertes.fr/tel-01064992.
Full textDeel, Troy A. "A statistical study of graph algorithms." Virtual Press, 1985. http://liblink.bsu.edu/uhtbin/catkey/424871.
Full textAnderson, Jon K. "Genetic algorithms applied to graph theory." Virtual Press, 1999. http://liblink.bsu.edu/uhtbin/catkey/1136714.
Full textDepartment of Computer Science
Newman, Alantha. "Algorithms for string and graph layout." Thesis, Massachusetts Institute of Technology, 2004. http://hdl.handle.net/1721.1/28745.
Full textIncludes bibliographical references (p. 121-125).
Many graph optimization problems can be viewed as graph layout problems. A layout of a graph is a geometric arrangement of the vertices subject to given constraints. For example, the vertices of a graph can be arranged on a line or a circle, on a two- or three-dimensional lattice, etc. The goal is usually to place all the vertices so as to optimize some specified objective function. We develop combinatorial methods as well as models based on linear and semidefinite programming for graph layout problems. We apply these techniques to some well-known optimization problems. In particular, we give improved approximation algorithms for the string folding problem on the two- and three-dimensional square lattices. This combinatorial graph problem is motivated by the protein folding problem, which is central in computational biology. We then present a new semidefinite programming formulation for the linear ordering problem (also known as the maximum acyclic subgraph problem) and show that it provides an improved bound on the value of an optimal solution for random graphs. This is the first relaxation that improves on the trivial "all edges" bound for random graphs.
by Alantha Newman.
Ph.D.
Yodpinyanee, Anak. "Sub-linear algorithms for graph problems." Thesis, Massachusetts Institute of Technology, 2018. http://hdl.handle.net/1721.1/120411.
Full textCataloged from PDF version of thesis.
Includes bibliographical references (pages 189-199).
In the face of massive data sets, classical algorithmic models, where the algorithm reads the entire input, performs a full computation, then reports the entire output, are rendered infeasible. To handle these data sets, alternative algorithmic models are suggested to solve problems under the restricted, namely sub-linear, resources such as time, memory or randomness. This thesis aims at addressing these limitations on graph problems and combinatorial optimization problems through a number of different models. First, we consider the graph spanner problem in the local computation algorithm (LCA) model. A graph spanner is a subgraph of the input graph that preserves all pairwise distances up to a small multiplicative stretch. Given a query edge from the input graph, the LCA explores a sub-linear portion of the input graph, then decides whether to include this edge in its spanner or not - the answers to all edge queries constitute the output of the LCA. We provide the first LCA constructions for 3 and 5-spanners of general graphs with almost optimal trade-offs between spanner sizes and stretches, and for fixed-stretch spanners of low maximum-degree graphs. Next, we study the set cover problem in the oracle access model. The algorithm accesses a sub-linear portion of the input set system by probing for elements in a set, and for sets containing an element, then computes an approximate minimum set cover: a collection of an approximately-minimum number of sets whose union includes all elements. We provide probe-efficient algorithms for set cover, and complement our results with almost tight lower bound constructions. We further extend our study to the LP-relaxation variants and to the streaming setting, obtaining the first streaming results for the fractional set cover problem. Lastly, we design local-access generators for a collection of fundamental random graph models. We demonstrate how to generate graphs according to the desired probability distribution in an on-the-fly fashion. Our algorithms receive probes about arbitrary parts of the input graph, then construct just enough of the graph to answer these probes, using only polylogarithmic time, additional space and random bits per probe. We also provide the first implementation of random neighbor probes, which is a basic algorithmic building block with applications in various huge graph models.
by Anak Yodpinyanee.
Ph. D.
Sun, Jiankai. "Directed Graph Analysis: Algorithms and Applications." The Ohio State University, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=osu1565797455907422.
Full textRen, Jintong. "Optimization algorithms for graph layout problems." Thesis, Angers, 2020. https://tel.archives-ouvertes.fr/tel-03178385.
Full textThis thesis considers two graph layout problems: the cyclic bandwidth problem (CBP) and the minimum linear arrangement problem (MinLA). The CBP is a natural extension of the bandwidth minimization problem (BMP) and the MinLA is a min-sum problem. These problems are widely applied in the real life. Since they are NP-hard problems, it is computational difficult to solve them in the general case. Therefore, this thesis is dedicated to developing effective heuristic algorithms to deal with these challenging problems.Specifically, we introduce two iterated local search algorithms, a memetic algorithm with different recombination operators for the CBP and a set based neighborhood heuristic algorithm to solve the MinLA. The two iterated local search algorithms are experimentallydemonstrated to be able to compete favourably with state-of-the-art methods, the feature of a suitable crossover for the memetic algorithm is identified for the CBP and the set based neighborhood heuristic algorithm is proven to be more efficient than the traditional 2-flip neighborhood algorithm
Neggazi, Brahim. "Self-stabilizing algorithms for graph parameters." Thesis, Lyon 1, 2015. http://www.theses.fr/2015LYO10041/document.
Full textThe concept of self-stabilization was first introduced by Dijkstra in 1973. A distributed system is self-stabilizing if it can start from any possible configuration and converges to a desired configuration in finite time by itself without using any external intervention. Convergence is also guaranteed when the system is affected by transient faults. This makes self-stabilization an effective approach for non-masking fault-tolerance. The self-stabilization was studied in various fields in distributed systems such as the problems of clock synchronization, communication and routing protocols. Given the importance of graph parameters, especially for organization and communication of networks and distributed systems, several self-stabilizing algorithms for classic graph parameters have been developed in this direction, such as self-stabilizing algorithms for finding minimal dominating sets, coloring, maximal matching, spanning tree and so on. Thence, we propose in this thesis, distributed and self-stabilizing algorithms to some wellknown graphs problems, particularly for graph decompositions and dominating sets problems that have not yet been addressed in a view of self-stabilization. The four major problems considered in this thesis are: the partitioning into triangles, p-star decomposition, edge monitoring set and independent strong dominating set problems. The common point between these four problems is that they are considered as variants of dominating set and matching problems and all propositions deal with the self-stabilization paradigm
Sun, Wen. "Heuristic Algorithms for Graph Coloring Problems." Thesis, Angers, 2018. http://www.theses.fr/2018ANGE0027/document.
Full textThis thesis concerns four NP-hard graph coloring problems, namely, graph coloring (GCP), equitable coloring (ECP), weighted vertex coloring (WVCP) and k-vertex-critical subgraphs (k-VCS). These problems are extensively studied in the literature not only for their theoretical intractability, but also for their real-world applications in many domains. Given that they belong to the class of NP-hard problems, it is computationally difficult to solve them exactly in the general case. For this reason, this thesis is devoted to developing effective heuristic approaches to tackle these challenging problems. We develop a reduction memetic algorithm (RMA) for the graph coloring problem, a feasible and infeasible search algorithm (FISA) for the equitable coloring problem, an adaptive feasible and infeasible search algorithm (AFISA) for the weighted vertex coloring problem and an iterated backtrack-based removal (IBR) algorithm for the k-VCS problem. All these algorithms were experimentally evaluated and compared with state-of-the-art methods
Sivanathan, Gowrishankar. "Sink free orientations in a graph." Diss., Online access via UMI:, 2009.
Find full textRinke, Sebastian. "Analysis and Adaption of Graph Mapping Algorithms for Regular Graph Topologies." Master's thesis, Universitätsbibliothek Chemnitz, 2009. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-200901453.
Full textSlade, Michael L. "A layout algorithm for hierarchical graphs with constraints /." Online version of thesis, 1994. http://hdl.handle.net/1850/11724.
Full textNewton, Matthew. "Sequential and parallel algorithms for low-crossing graph drawing." Thesis, Loughborough University, 2007. https://dspace.lboro.ac.uk/2134/12944.
Full textJayachandran, Jayakanth. "Improving resiliency using graph based evolutionary algorithms." Diss., Rolla, Mo. : Missouri University of Science and Technology, 2010. http://scholarsmine.mst.edu/thesis/pdf/Jayachandran_09007dcc807d6ba6.pdf.
Full textVita. The entire thesis text is included in file. Title from title screen of thesis/dissertation PDF file (viewed July 19, 2010) Includes bibliographical references (p. 56-62).
McConville, Ryan. "Clustering algorithms for large scale graph data." Thesis, Queen's University Belfast, 2017. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.727648.
Full textLiang, Weifa, and wliang@cs anu edu au. "Designing Efficient Parallel Algorithms for Graph Problems." The Australian National University. Department of Computer Science, 1997. http://thesis.anu.edu.au./public/adt-ANU20010829.114536.
Full textOrtmann, Mark [Verfasser]. "Combinatorial Algorithms for Graph Sparsification / Mark Ortmann." Konstanz : Bibliothek der Universität Konstanz, 2017. http://d-nb.info/1173616438/34.
Full textChong, Ka-wong, and 莊家旺. "Improved algorithms for some classical graph problems." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 1996. http://hub.hku.hk/bib/B31234793.
Full textHolloway, Nick. "Parallel algorithms in graph theory and algebra." Thesis, University of Warwick, 1994. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.338724.
Full textGhaffari, Mohsen. "Improved distributed algorithms for fundamental graph problems." Thesis, Massachusetts Institute of Technology, 2017. http://hdl.handle.net/1721.1/109000.
Full textCataloged from PDF version of thesis.
Includes bibliographical references (pages 237-255).
Distributed graph algorithms provide efficient and theoretically sound methods for solving graph problems in distributed settings and more generally for performing distributed computation in networks. These algorithms are applicable in a wide variety of settings, ranging from computer networks to massively parallel computing and beyond. This thesis addresses a number of the central problems of distributed graph algorithms. These problems generally revolve around two of the principal challenges of the area, locality and congestion. The problems include computing maximal independent set, minimum spanning tree, minimum edge cut and minimum vertex cut, graph connectivity decompositions, network information dissemination, minimum-weight connected dominating set, and scheduling distributed protocols. We develop novel techniques, concepts, and tools for these problems, and present algorithms and impossibility results which improve considerably on the state of the art, in several cases resolving or advancing long-standing open problems.
by Mohsen Ghaffari.
Ph. D.
Nguyen, Huy Ngoc Ph D. Massachusetts Institute of Technology. "Constant time algorithms in sparse graph model." Thesis, Massachusetts Institute of Technology, 2010. http://hdl.handle.net/1721.1/62426.
Full textCataloged from PDF version of thesis.
Includes bibliographical references (p. 87-91).
We focus on constant-time algorithms for graph problems in bounded degree model. We introduce several techniques to design constant-time approximation algorithms for problems such as Vertex Cover, Maximum Matching, Maximum Weighted Matching, Maximum Independent Set and Set Cover. Some of our techniques can also be applied to design constant-time testers for minor-closed properties. In Chapter 1, we show how to construct a simple oracle that provides query access to a fixed Maximal Independent Set (MIS) of the input graph. More specifically, the oracle gives answers to queries of the form "Is v in the MIS?" for any vertex v in the graph. The oracle runs in constant-time, i.e., the running time for the oracle to answer a single query, is independent to the size of the input graph. Combining this oracle with a simple sampling scheme immediately implies an approximation algorithm for size of the minimum vertex cover. The second technique, called oracle hierarchy, transforms classical approximation algorithms into constant-time algorithms that approximate the size of the optimal solution. The technique is applicable to a certain subclass of algorithms that compute a solution in a constant number of phases. In the transformation, oracle hierarchy uses the MIS oracle to simulates each phase. The problems amenable to these techniques include Maximum Matching, Maximum Weight Matching, Set Cover, and Minimum Dominating Set. For example, for Maximum Matching, we give the first constant-time algorithm that for the class of graphs of degree bounded by d, computes the maximum matching size to within en, for any e > 0, where n is the number of vertices in the graph. The running time of the algorithm is independent of n, and only depends on d and e. In Chapter 2, we introduce a new tool called partitioning oracle which provides query access to a fixed partition of the input graph. In particular, the oracle gives answers to queries of the form "Which part in the fixed partition contains v?" for any vertex v in the graph. We develop methods for constructing a partitioning oracle for any class of bounded-degree graphs with an excluded minor. For any e > 0, our partitioning oracle provides query access to a fixed partition of the input constant-degree minor-free graph, in which every part has size 0(1/ 2 ), and the number of edges removed is at most en. We illustrate the power of this technique by using it to extend and simplify a number of previous approximation and testing results for sparse graphs, as well as to provide new results that were unachievable with existing techniques. For instance: " We give constant-time approximation algorithms for the size of the minimum vertex cover, the minimum dominating set, and the maximum independent set for any class of graphs with an excluded minor. * We show a simple proof that any minor-closed graph property is testable in constant time in the bounded degree model. Finally, in Chapter 3, we construct a more efficient partitioning oracle for graphs with constant treewidth. Although the partitioning oracle in Chapter 2 runs in time independent of the size of the input graph, it has to make 2POlY(1/E)) queries to the input graph to answer a query about the partition. Our new partitioning oracle improves this query complexity to poly(1/E) for graphs with constant treewidth. The new oracle can be used to test constant treewidth in poly(1/E) time in the bounded-degree model. Another application is a poly(1/E)-time algorithm that approximates the maximum matching size, the minimum vertex cover size, and the minimum dominating set size up to an additive en in bounded treewidth graphs.
by Huy Ngoc Nguyen.
Ph.D.
Hasenplaugh, William Cleaburn. "Parallel algorithms for scheduling data-graph computations." Thesis, Massachusetts Institute of Technology, 2016. http://hdl.handle.net/1721.1/103666.
Full textThis 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 169-182).
A data-graph computation - popularized by such programming systems as Pregel, GraphLab, Galois, Ligra, PowerGraph, and GraphChi - is an algorithm that iteratively performs local updates on the vertices of a graph. During each round of a data-graph computation, a user-supplied update function atomically modifies the data associated with a vertex as a function of the vertex's prior data and that of adjacent vertices. A dynamic data-graph computation updates only an active subset of the vertices during a round, and those updates determine the set of active vertices for the next round. In this thesis, I explore two ways of scheduling deterministic parallel data-graph computations that provide performance guarantees culminating in theoretical contributions to graph theory and practical, high-performance systems. In particular, I describe a system called Prism which processes dynamic and static data-graph computations on arbitrary graphs using a technique called chromatic scheduling. Using a vertex-coloring to identify independent sets of vertices, which may be safely processed in parallel, Prism serializes through the colors and processes the independent sets in parallel, thus executing data-graph computations deterministically and without the use of costly atomic instructions (e.g., Compare-And-Swap). Prism supports dynamic data-graph computations deterministically and work-efficiently through the introduction of multibag and multivector data structures. Prism requires a vertex-coloring, and since graphs are generally not supplied with one, it is necessary to find one as a preprocessing step. Furthermore, the runtime of Prism is linear in the number of colors and thus motivates a study in this thesis of fast parallel coloring algorithms that provide vertex-colorings with few colors in practice. At the core of the analysis of these coloring algorithms lies a new result about the maximum depth of a random priority dag, the dag that results from randomly ordering vertices and directing edges from lower to higher numbered vertices in the order. In particular, when the largest degree [delta] in the graph G = (V,E) is less than ln !V !, I show a tight bound on the longest path: [theta](ln V / ln (e ln V / [delta])) with high probability. When [delta] is greater than ln !V!, the longest path in the dag is simply [theta] (min {[delta], [square root sign]E}) , also with high probability. I also present a system called Laika which processes data-graph computations for the special, but important, case of graphs representing physical simulations. Such graphs typically have vertices with coordinates in 3D space and are connected to other "nearby" vertices. We take advantage of these two properties to execute physical simulations, cast as data-graph computations, that make efficient use of cache resources. I analyze a contrived graph construction - a random cube graph - as a proxy for the mesh graphs that arise in physical simulations: n vertices are uniformly randomly assigned positions in the unit cube and have edges connecting them to any other vertices that are within a distance r = O (V -¹/³) . For such a graph and given a cache sufficiently large to hold M vertices, I improve on previous theory to show that a fraction O(M-¹/³) of edges will connect to vertices not in the cache, whereas previous theory held that this "miss rate" is O(M-¹/⁴). Laika also guarantees linear speedup for any random cube graph G = (V,E) with constant average degree for any number of workers P = O (V= lg² V).
by William Cleaburn Hasenplaugh.
Ph. D.
Ka-wong, Chong. "Improved algorithms for some classical graph problems /." Hong Kong : University of Hong Kong, 1996. http://sunzi.lib.hku.hk/hkuto/record.jsp?B19668508.
Full textSoleimanfallah, Arezou. "Fixed-parameter tractable algorithms in graph theory." Thesis, Royal Holloway, University of London, 2010. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.531326.
Full textCRUCIANI, EMILIO. "Simple Randomized Distributed Algorithms for Graph Clustering." Doctoral thesis, Gran Sasso Science Institute, 2019. http://hdl.handle.net/20.500.12571/9951.
Full textNourbakhsh, Farshad <1979>. "Algorithms for graph compression : theory and experiments." Doctoral thesis, Università Ca' Foscari Venezia, 2014. http://hdl.handle.net/10579/5639.
Full textLee, William W. L. (William Wai Lam) Carleton University Dissertation Computer Science. "Tree editing algorithms." Ottawa, 1992.
Find full textGajewar, Amita Surendra. "Approximate edge 3-coloring of cubic graphs." Thesis, Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/29735.
Full textCommittee Chair: Prof. Richard Lipton; Committee Member: Prof. Dana Randall; Committee Member: Prof. H. Venkateswaran. Part of the SMARTech Electronic Thesis and Dissertation Collection.
Ediger, David. "Analyzing hybrid architectures for massively parallel graph analysis." Diss., Georgia Institute of Technology, 2013. http://hdl.handle.net/1853/47659.
Full textWarty, Durgesh A. "Development of Graphcards a hypertext system for learning graph theory and graph algorithms." Virtual Press, 1998. http://liblink.bsu.edu/uhtbin/catkey/1101590.
Full textDepartment of Computer Science
Peternek, Fabian Hans Adolf. "Graph compression using graph grammars." Thesis, University of Edinburgh, 2018. http://hdl.handle.net/1842/31094.
Full textColes, Jonathan. "Algorithms for bounding Folkman numbers /." Online version of thesis, 2005. https://ritdml.rit.edu/dspace/handle/1850/2765.
Full textSulong, Ghazali bin. "Algorithms for timetable construction." Thesis, Cardiff University, 1989. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.253664.
Full textSchwartz, Victor Scott. "Dynamic platform-independent meta-algorithms for graph-partitioning." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 1998. http://handle.dtic.mil/100.2/ADA356541.
Full textThesis advisor(s): Gordon H. Bradley. "September 1998." Includes bibliographical references (p. 99-100). Also available online.
Preisinger, Timotheus. "Graph-based algorithms for Pareto preference query evaluation." Norderstedt Books on Demand, 2009. http://d-nb.info/1000465993/34.
Full textCano, Vila María del Pilar. "Generalized Delaunay triangulations : graph-theoretic properties and algorithms." Doctoral thesis, Universitat Politècnica de Catalunya, 2020. http://hdl.handle.net/10803/669310.
Full textEsta tesis estudia diferentes generalizaciones de la triangulación de Delaunay, tanto desde un punto de vista combinatorio como algorítmico. La triangulación de Delaunay de un conjunto de puntos S, denotada DT(S), tiene como conjunto de vértices a S. Una arista uv está en DT(S) si satisface la propiedad del círculo vacío: existe un círculo con u y v en su frontera que no contiene ningún punto de S en su interior. Debido a distintos criterios de optimización, se han propuesto varias generalizaciones de la DT (S). Hoy en día, se conocen bastantes propiedades de la DT(S), sin embargo, poco se sabe sobre sus generalizaciones. La pregunta principal que exploramos es: ¿Hasta qué punto las propiedades de la DT(S) se pueden extender para generalizaciones de gráficas de Delaunay? Primero, exploramos la conectividad de la gráfica de flips de las triangulaciones de Delaunay de orden alto de un conjunto de puntos S en el plano. La gráfica de flips de triangulaciones de orden k = 3 podría ser disconexa, sin embargo, nosotros damos una cota superior e inferior para la distancia en flips de una triangulación de orden k a alguna otra cuando S cumple con ciertas características. Luego, probamos que existe una secuencia de árboles generadores sin cruces tal que la suma total de la longitud de las aristas con respecto a una distancia convexa arbitraria es decreciente y converge al árbol generador mínimo con respecto a la distancia correspondiente. Cada par de árboles consecutivos en la secuencia se encuentran en una triangulación de Delaunay con restricciones. Adicionalmente, damos una cota superior lineal para la longitud de la secuencia y cotas específicas cuando el conjunto convexo es un cuadrado. Aún concentrados en distancias convexas, estudiamos hamiltonicidad en las gráficas de Delaunay de distancia convexa de k-orden. Dependiendo en la distancia convexa, exhibimos diversas cotas superiores para el mínimo valor de k que satisface que la gráfica de Delaunay de distancia convexa de orden-k es hamiltoniana. También damos cotas inferiores para k cuando el conjunto convexo pertenece a un conjunto de ciertos polígonos regulares. Finalmente, re-visitamos una triangulación afín invariante, la cual es un caso especial de triangulación de Delaunay de distancia convexa. Probamos que muchas propiedades de la triangulación de Delaunay estándar se preservan en estas triangulaciones. Además, motivados por esta triangulación afín invariante, estudiamos diferentes algoritmos que producen otros objetos geométricos afín invariantes.
Danilenko, Nikita [Verfasser]. "Designing Functional Implementations of Graph Algorithms / Nikita Danilenko." Kiel : Universitätsbibliothek Kiel, 2016. http://d-nb.info/1102933031/34.
Full text