Relevant bibliographies by topics / Graph algorithms

Academic literature on the topic 'Graph algorithms'

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

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

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources 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.

Journal articles on the topic "Graph algorithms"

1

Chen, Yuzhong, Zhenyu Liu, Yulin Liu, and Chen Dong. "Distributed Attack Modeling Approach Based on Process Mining and Graph Segmentation." Entropy 22, no. 9 (September 14, 2020): 1026. http://dx.doi.org/10.3390/e22091026.

Full text
Abstract:
Attack graph modeling aims to generate attack models by investigating attack behaviors recorded in intrusion alerts raised in network security devices. Attack models can help network security administrators discover an attack strategy that intruders use to compromise the network and implement a timely response to security threats. However, the state-of-the-art algorithms for attack graph modeling are unable to obtain a high-level or global-oriented view of the attack strategy. To address the aforementioned issue, considering the similarity between attack behavior and workflow, we employ a heuristic process mining algorithm to generate the initial attack graph. Although the initial attack graphs generated by the heuristic process mining algorithm are complete, they are extremely complex for manual analysis. To improve their readability, we propose a graph segmentation algorithm to split a complex attack graph into multiple subgraphs while preserving the original structure. Furthermore, to handle massive volume alert data, we propose a distributed attack graph generation algorithm based on Hadoop MapReduce and a distributed attack graph segmentation algorithm based on Spark GraphX. Additionally, we conduct comprehensive experiments to validate the performance of the proposed algorithms. The experimental results demonstrate that the proposed algorithms achieve considerable improvement over comparative algorithms in terms of accuracy and efficiency.
APA, Harvard, Vancouver, ISO, and other styles
2

Ji, Shengwei, Chenyang Bu, Lei Li, and Xindong Wu. "Local Graph Edge Partitioning." ACM Transactions on Intelligent Systems and Technology 12, no. 5 (October 31, 2021): 1–25. http://dx.doi.org/10.1145/3466685.

Full text
Abstract:
Graph edge partitioning, which is essential for the efficiency of distributed graph computation systems, divides a graph into several balanced partitions within a given size to minimize the number of vertices to be cut. Existing graph partitioning models can be classified into two categories: offline and streaming graph partitioning models. The former requires global graph information during the partitioning, which is expensive in terms of time and memory for large-scale graphs. The latter creates partitions based solely on the received graph information. However, the streaming model may result in a lower partitioning quality compared with the offline model. Therefore, this study introduces a Local Graph Edge Partitioning model, which considers only the local information (i.e., a portion of a graph instead of the entire graph) during the partitioning. Considering only the local graph information is meaningful because acquiring complete information for large-scale graphs is expensive. Based on the Local Graph Edge Partitioning model, two local graph edge partitioning algorithms—Two-stage Local Partitioning and Adaptive Local Partitioning—are given. Experimental results obtained on 14 real-world graphs demonstrate that the proposed algorithms outperform rival algorithms in most tested cases. Furthermore, the proposed algorithms are proven to significantly improve the efficiency of the real graph computation system GraphX.
APA, Harvard, Vancouver, ISO, and other styles
3

Li, Jonathan, Rohan Potru, and Farhad Shahrokhi. "A Performance Study of Some Approximation Algorithms for Computing a Small Dominating Set in a Graph." Algorithms 13, no. 12 (December 14, 2020): 339. http://dx.doi.org/10.3390/a13120339.

Full text
Abstract:
We implement and test the performances of several approximation algorithms for computing the minimum dominating set of a graph. These algorithms are the standard greedy algorithm, the recent Linear programming (LP) rounding algorithms and a hybrid algorithm that we design by combining the greedy and LP rounding algorithms. Over the range of test data, all algorithms perform better than anticipated in theory, and have small performance ratios, measured as the size of output divided by the LP objective lower bound. However, each have advantages over the others. For instance, LP rounding algorithm normally outperforms the other algorithms on sparse real-world graphs. On a graph with 400,000+ vertices, LP rounding took less than 15 s of CPU time to generate a solution with performance ratio 1.011, while the greedy and hybrid algorithms generated solutions of performance ratio 1.12 in similar time. For synthetic graphs, the hybrid algorithm normally outperforms the others, whereas for hypercubes and k-Queens graphs, greedy outperforms the rest. Another advantage of the hybrid algorithm is to solve very large problems that are suitable for application of LP rounding (sparse graphs) but LP formulations become formidable in practice and LP solvers crash, as we observed on a real-world graph with 7.7 million+ vertices and a planar graph on 1,000,000 vertices.
APA, Harvard, Vancouver, ISO, and other styles
4

Dib, Fadi K., and Peter Rodgers. "Graph drawing using Jaya." PLOS ONE 18, no. 6 (June 27, 2023): e0287744. http://dx.doi.org/10.1371/journal.pone.0287744.

Full text
Abstract:
Graph drawing, involving the automatic layout of graphs, is vital for clear data visualization and interpretation but poses challenges due to the optimization of a multi-metric objective function, an area where current search-based methods seek improvement. In this paper, we investigate the performance of Jaya algorithm for automatic graph layout with straight lines. Jaya algorithm has not been previously used in the field of graph drawing. Unlike most population-based methods, Jaya algorithm is a parameter-less algorithm in that it requires no algorithm-specific control parameters and only population size and number of iterations need to be specified, which makes it easy for researchers to apply in the field. To improve Jaya algorithm’s performance, we applied Latin Hypercube Sampling to initialize the population of individuals so that they widely cover the search space. We developed a visualization tool that simplifies the integration of search methods, allowing for easy performance testing of algorithms on graphs with weighted aesthetic metrics. We benchmarked the Jaya algorithm and its enhanced version against Hill Climbing and Simulated Annealing, commonly used graph-drawing search algorithms which have a limited number of parameters, to demonstrate Jaya algorithm’s effectiveness in the field. We conducted experiments on synthetic datasets with varying numbers of nodes and edges using the Erdős–Rényi model and real-world graph datasets and evaluated the quality of the generated layouts, and the performance of the methods based on number of function evaluations. We also conducted a scalability experiment on Jaya algorithm to evaluate its ability to handle large-scale graphs. Our results showed that Jaya algorithm significantly outperforms Hill Climbing and Simulated Annealing in terms of the quality of the generated graph layouts and the speed at which the layouts were produced. Using improved population sampling generated better layouts compared to the original Jaya algorithm using the same number of function evaluations. Moreover, Jaya algorithm was able to draw layouts for graphs with 500 nodes in a reasonable time.
APA, Harvard, Vancouver, ISO, and other styles
5

SKULRATTANAKULCHAI, SAN, and HAROLD N. GABOW. "COLORING ALGORITHMS ON SUBCUBIC GRAPHS." International Journal of Foundations of Computer Science 15, no. 01 (February 2004): 21–40. http://dx.doi.org/10.1142/s0129054104002285.

Full text
Abstract:
We present efficient algorithms for three coloring problems on subcubic graphs. (A subcubic graph has maximum degree at most three.) The first algorithm is for 4-edge coloring, or more generally, 4-list-edge coloring. Our algorithm runs in linear time, and appears to be simpler than previous ones. The second algorithm is the first randomized EREW PRAM algorithm for the same problem. It uses O(n/ log n) processors and runs in O( log n) time with high probability, where n is the number of vertices of the graph. The third algorithm is the first linear-time algorithm to 5-total-color subcubic graphs. The fourth algorithm generalizes this to get the first linear-time algorithm to 5-list-total-color subcubic graphs. Our sequential algorithms are based on a method of ordering the vertices and edges by traversing a spanning tree of a graph in a bottom-up fashion. Our parallel algorithm is based on a simple decomposition principle for subcubic graphs.
APA, Harvard, Vancouver, ISO, and other styles
6

RAJASEKARAN, SANGUTHEVAR, and VAMSI KUNDETI. "SPECTRUM BASED TECHNIQUES FOR GRAPH ISOMORPHISM." International Journal of Foundations of Computer Science 20, no. 03 (June 2009): 479–99. http://dx.doi.org/10.1142/s0129054109006693.

Full text
Abstract:
The graph isomorphism problem is to check if two given graphs are isomorphic. Graph isomorphism is a well studied problem and numerous algorithms are available for its solution. In this paper we present algorithms for graph isomorphism that employ the spectra of graphs. An open problem that has fascinated many a scientist is if there exists a polynomial time algorithm for graph isomorphism. Though we do not solve this problem in this paper, the algorithms we present take polynomial time. These algorithms have been tested on a good collection of instances. However, we have not been able to prove that our algorithms will work on all possible instances. In this paper, we also give a new construction for cospectral graphs.
APA, Harvard, Vancouver, ISO, and other styles
7

Saeed, Ayesha, Ali Husnain, Anam Zahoor, and Mehmood Gondal. "A Comparative Study of Cat Swarm Algorithm for Graph Coloring Problem: Convergence Analysis and Performance Evaluation." International Journal of Innovative Research in Computer Science and Technology 12, no. 4 (July 2024): 1–9. http://dx.doi.org/10.55524/ijircst.2024.12.4.1.

Full text
Abstract:
The Graph Coloring Problem (GCP) is a significant optimization challenge widely suitable to solve scheduling problems. Its goal is to specify the minimum colors (k) required to color a graph properly. Due to its NP-completeness, exact algorithms become impractical for graphs exceeding 100 vertices. As a result, approximation algorithms have gained prominence for tackling large-scale instances. In this context, the Cat Swarm algorithm, a novel population-based metaheuristic in the domain of swarm intelligence, has demonstrated promising convergence properties compared to other population-based algorithms. This research focuses on designing and implementing the Cat Swarm algorithm to address the GCP. By conducting a comparative study with established algorithms, our investigation revolves around quantifying the minimum value of k required by the Cat Swarm algorithm for each graph instance. The evaluation metrics include the algorithm's running time in seconds, success rate, and the mean count of iterations or assessments required to reach a goal.
APA, Harvard, Vancouver, ISO, and other styles
8

Serratosa, Francesc. "A Methodology to Generate Attributed Graphs with a Bounded Graph Edit Distance for Graph-Matching Testing." International Journal of Pattern Recognition and Artificial Intelligence 32, no. 11 (July 24, 2018): 1850038. http://dx.doi.org/10.1142/s0218001418500386.

Full text
Abstract:
This paper presents a methodology for generating pairs of attributed graphs with a lower and upper- bounded graph edit distance (GED). It is independent of the type of attributes on nodes and edges. The algorithm is composed of three steps: randomly generating a graph, generating another graph as a sub-graph of the first, and adding structural and semantic noise to both. These graphs, together with their bounded distances, can be used to manufacture synthetic databases of large graphs. The exact GED between large graphs cannot be obtained for runtime reasons since it has to be computed through an optimal algorithm with an exponential computational cost. Through this database, we can test the behavior of the known or new sub-optimal error-tolerant graph-matching algorithms against a lower and an upper bound GED on large graphs, even though we do not have the true distance. It is not clear how the error induced by the use of sub-optimal algorithms grows with problem size. Thus, with this methodology, we can generate graph databases and analyze if the current assumption that we can extrapolate algorithms’ behavior from matching small graphs to large graphs is correct or not. We also show that with some restrictions, the methodology returns the optimal GED in a quadratic time and that it can also be used to generate graph databases to test exact sub-graph isomorphism algorithms.
APA, Harvard, Vancouver, ISO, and other styles
9

Manaster, Alfred B., Jeffrey B. Remmel, and James H. Schmerl. "Planarity and minimal path algorithms." Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics 40, no. 1 (February 1986): 131–42. http://dx.doi.org/10.1017/s1446788700026550.

Full text
Abstract:
AbstractIn 1981 two notions of effective presentation of countable connected graphs were formulated by J. C. E. Dekker—namely, edge recognition algorithm graphs and minimal path algorithm graphs. In this paper we show that every planar graph has a minimal path algorithm presentation but that some graphs have no minimal path algorithm presentations. We introduce the notion of a shortest distance algorithm graph, show that it lies strictly between the two notions of Dekker, and show that every graph has a shortest distance algorithm presentation. Finally, in contrast to Dekker's result about minimal path algorithm graphs, we produce a shortest distance algorithm graph which has no spanning tree which is an edge recognition algorithm graph.
APA, Harvard, Vancouver, ISO, and other styles
10

GODDARD, WAYNE, STEPHEN T. HEDETNIEMI, DAVID P. JACOBS, and PRADIP K. SRIMANI. "SELF-STABILIZING ALGORITHMS FOR ORDERINGS AND COLORINGS." International Journal of Foundations of Computer Science 16, no. 01 (February 2005): 19–36. http://dx.doi.org/10.1142/s012905410500284x.

Full text
Abstract:
A k-forward numbering of a graph is a labeling of the nodes with integers such that each node has less than k neighbors whose labels are equal or larger. Distributed algorithms that reach a legitimate state, starting from any illegitimate state, are called self-stabilizing. We obtain three self-stabilizing (s-s) algorithms for finding a k-forward numbering, provided one exists. One such algorithm also finds the k-height numbering of graph, generalizing s-s algorithms by Bruell et al. [4] and Antonoiu et al. [1] for finding the center of a tree. Another k-forward numbering algorithm runs in polynomial time. The motivation of k-forward numberings is to obtain new s-s graph coloring algorithms. We use a k-forward numbering algorithm to obtain an s-s algorithm that is more general than previous coloring algorithms in the literature, and which k-colors any graph having a k-forward numbering. Special cases of the algorithm 6-color planar graphs, thus generalizing an s-s algorithm by Ghosh and Karaata [13], as well as 2-color trees and 3-color series-parallel graphs. We discuss how our s-s algorithms can be extended to the synchronous model.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Graph algorithms"

1

Zhou, Hang. "Graph algorithms : network inference and planar graph optimization." Thesis, Paris, Ecole normale supérieure, 2015. http://www.theses.fr/2015ENSU0016/document.

Full text
Abstract:
Cette thèse porte sur deux sujets d’algorithmique des graphes. Le premier sujet est l’inférence de réseaux. Quelle est la complexité pour déterminer un graphe inconnu à partir de requêtes de plus court chemin entre ses sommets ? Nous supposons que le graphe est de degré borné. Dans le problème de reconstruction, le but est de reconstruire le graphe ; tandis que dans le problème de vérification, le but est de vérifier qu’un graphe donné est correct. Nous développons des algorithmes probabilistes utilisant une décomposition en cellules de Voronoi. Ensuite, nous analysons des algorithmes de type glouton, et montrons qu’ils sont quasi-optimaux. Nous étudions aussi ces problèmes sur des familles particulières de graphes, démontrons des bornes inférieures, et étudions la reconstruction approximative. Le deuxième sujet est l’étude de deux problèmes d’optimisation sur les graphes planaires. Dans le problème de classification par corrélations, l’entrée est un graphe pondéré, où chaque arête a une étiquette h+i ou h-i, indiquant si ses extrémités sont ou non dans la même catégorie. Le but est de trouver une partition des sommets en catégories qui respecte au mieux les étiquettes. Dans le problème d’augmentation 2-arête-connexe, l’entrée est un graphe pondéré et un sous-ensemble R des arêtes. Le but est de trouver un sous-ensemble S des arêtes de poids minimum, tel que pour chaque arête de R, ses extrémités sont dans une composante 2-arête-connexe de l’union de R et S. Pour les graphes planaires, nous réduisons le premier problème au deuxième et montrons que les deux problèmes, bien que NP-durs, ont un schéma d’approximation en temps polynomial. Nous utilisons la technique récente de décomposition en briques
This 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
APA, Harvard, Vancouver, ISO, and other styles
2

Bui, Thang Nguyen. "Graph bisection algorithms." Thesis, Massachusetts Institute of Technology, 1986. http://hdl.handle.net/1721.1/77680.

Full text
Abstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1986.
MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING.
Bibliography: leaves 64-66.
by Thang Nguyen Bui.
Ph.D.
APA, Harvard, Vancouver, ISO, and other styles
3

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 text
Abstract:

In 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.

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

Profiti, Giuseppe <1980&gt. "Graph algorithms for bioinformatics." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amsdottorato.unibo.it/6914/1/profiti_giuseppe_tesi.pdf.

Full text
Abstract:
Biological data are inherently interconnected: protein sequences are connected to their annotations, the annotations are structured into ontologies, and so on. While protein-protein interactions are already represented by graphs, in this work I am presenting how a graph structure can be used to enrich the annotation of protein sequences thanks to algorithms that analyze the graph topology. We also describe a novel solution to restrict the data generation needed for building such a graph, thanks to constraints on the data and dynamic programming. The proposed algorithm ideally improves the generation time by a factor of 5. The graph representation is then exploited to build a comprehensive database, thanks to the rising technology of graph databases. While graph databases are widely used for other kind of data, from Twitter tweets to recommendation systems, their application to bioinformatics is new. A graph database is proposed, with a structure that can be easily expanded and queried.
APA, Harvard, Vancouver, ISO, and other styles
5

Profiti, Giuseppe <1980&gt. "Graph algorithms for bioinformatics." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2015. http://amsdottorato.unibo.it/6914/.

Full text
Abstract:
Biological data are inherently interconnected: protein sequences are connected to their annotations, the annotations are structured into ontologies, and so on. While protein-protein interactions are already represented by graphs, in this work I am presenting how a graph structure can be used to enrich the annotation of protein sequences thanks to algorithms that analyze the graph topology. We also describe a novel solution to restrict the data generation needed for building such a graph, thanks to constraints on the data and dynamic programming. The proposed algorithm ideally improves the generation time by a factor of 5. The graph representation is then exploited to build a comprehensive database, thanks to the rising technology of graph databases. While graph databases are widely used for other kind of data, from Twitter tweets to recommendation systems, their application to bioinformatics is new. A graph database is proposed, with a structure that can be easily expanded and queried.
APA, Harvard, Vancouver, ISO, and other styles
6

Bessy, 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 text
Abstract:
This document is a long abstract of my research work, concerning graph theory and algorithms on graphs. It summarizes some results, gives ideas of the proof for some of them and presents the context of the different topics together with some interesting open questions connected to them The first part precises the notations used in the rest of the paper; the second part deals with some problems on cycles in digraphs; the third part is an overview of two graph coloring problems and one problem on structures in colored graphs; finally the fourth part focus on some results in algorithmic graph theory, mainly in parametrized complexity.
APA, Harvard, Vancouver, ISO, and other styles
7

Stewart, Anthony Graham. "Graph algorithms and complexity aspects on special graph classes." Thesis, Durham University, 2017. http://etheses.dur.ac.uk/12144/.

Full text
Abstract:
Graphs are a very flexible tool within mathematics, as such, numerous problems can be solved by formulating them as an instance of a graph. As a result, however, some of the structures found in real world problems may be lost in a more general graph. An example of this is the 4-Colouring problem which, as a graph problem, is NP-complete. However, when a map is converted into a graph, we observe that this graph has structural properties, namely being (K_5, K_{3,3})-minor-free which can be exploited and as such there exist algorithms which can find 4-colourings of maps in polynomial time. This thesis looks at problems which are NP-complete in general and determines the complexity of the problem when various restrictions are placed on the input, both for the purpose of finding tractable solutions for inputs which have certain structures, and to increase our understanding of the point at which a problem becomes NP-complete. This thesis looks at four problems over four chapters, the first being Parallel Knock-Out. This chapter will show that Parallel Knock-Out can be solved in O(n+m) time on P_4-free graphs, also known as cographs, however, remains hard on split graphs, a subclass of P_5-free graphs. From this a dichotomy is shown on $P_k$-free graphs for any fixed integer $k$. The second chapter looks at Minimal Disconnected Cut. Along with some smaller results, the main result in this chapter is another dichotomy theorem which states that Minimal Disconnected Cut is polynomial time solvable for 3-connected planar graphs but NP-hard for 2-connected planar graphs. The third chapter looks at Square Root. Whilst a number of results were found, the work in this thesis focuses on the Square Root problem when restricted to some classes of graphs with low clique number. The final chapter looks at Surjective H-Colouring. This chapter shows that Surjective H-Colouring is NP-complete, for any fixed, non-loop connected graph H with two reflexive vertices and for any fixed graph H’ which can be obtained from H by replacing vertices with true twins. This result enabled us to determine the complexity of Surjective H-Colouring on all fixed graphs H of size at most 4.
APA, Harvard, Vancouver, ISO, and other styles
8

Freeth, S. A. "Compression methods for graph algorithms." Thesis, University of Canterbury. Computer Science, 1985. http://hdl.handle.net/10092/9568.

Full text
Abstract:
Two compression methods for representing graphs are presented, in conjunction with algorithms applying these methods. A decomposition technique for networks that can be generated in O(m) time is presented. The components of the decomposition and the shortest path matrix of the compressed network can be used to find the shortest path between any pair of vertices in the original network in linear time. A compression method for boolean matrices and a method for applying the compression to boolean matrix multiplication is developed. The algorithms have an expected running time of O(n²*log ₂n). From this compression method a simple heuristic that may be applied to any algorithm for boolean matrix multiplication has been developed. This heuristic will improve the average running time of boolean matrix multiplication algorithms. An order of magnitude analysis of the results published by Loukakis and Tsouris [1981], on the efficiency of algorithms for finding all maximal independent sets of a graph has been performed. This analysis showed that their conclusions, which are based on a direct comparison of the running times of the algorithms, do not take into account implementation factors. An average constant factor improvement is developed for the algorithm of Tsukiyama, Ide, Ariyoshi and Shirakawa [1977] for finding all maximal independent sets of a graph. Analysis of the running time results from the algorithm comparisons presented in this thesis show that the Bron-Kerbosch algorithm has the smallest rate of increase in running time as the size of the graphs increase.
APA, Harvard, Vancouver, ISO, and other styles
9

Ren, Chenghui, and 任成會. "Algorithms for evolving graph analysis." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2014. http://hdl.handle.net/10722/197105.

Full text
Abstract:
In many applications, entities and their relationships are represented by graphs. Examples include social networks (users and friendship), the WWW (web pages and hyperlinks) and bibliographic networks (authors and co-authorship). In a dynamic world, information changes and so the graphs representing the information evolve with time. For example, a Facebook link between two friends is established, or a hyperlink is added to a web page. We propose that historical graph-structured data be archived for analytical processing. We call a historical evolving graph sequence an EGS. We study the problem of efficient query processing on an EGS, which finds many applications that lead to interesting evolving graph analysis. To solve the problem, we propose a solution framework called FVF and a cluster-based LU decomposition algorithm called CLUDE, which can evaluate queries efficiently to support EGS analysis. The Find-Verify-and-Fix (FVF) framework applies to a wide range of queries. We demonstrate how some important graph measures, including shortest-path distance, closeness centrality and graph centrality, can be efficiently computed from EGSs using FVF. Since an EGS generally contains numerous large graphs, we also discuss several compact storage models that support our FVF framework. Through extensive experiments on both real and synthetic datasets, we show that our FVF framework is highly efficient in EGS query processing. A graph can be conveniently modeled by a matrix from which various quantitative measures are derived like PageRank and SALSA and Personalized PageRank and Random Walk with Restart. To compute these measures, linear systems of the form Ax = b, where A is a matrix that captures a graph's structure, need to be solved. To facilitate solving the linear system, the matrix A is often decomposed into two triangular matrices (L and U). In a dynamic world, the graph that models it changes with time and thus is the matrix A that represents the graph. We consider a sequence of evolving graphs and its associated sequence of evolving matrices. We study how LU-decomposition should be done over the sequence so that (1) the decomposition is efficient and (2) the resulting LU matrices best preserve the sparsity of the matrices A's (i.e., the number of extra non-zero entries introduced in L and U are minimized). We propose a cluster-based algorithm CLUDE for solving the problem. Through an experimental study, we show that CLUDE is about an order of magnitude faster than the traditional incremental update algorithm. The number of extra non-zero entries introduced by CLUDE is also about an order of magnitude fewer than that of the traditional algorithm. CLUDE is thus an efficient algorithm for LU decomposition that produces high-quality LU matrices over an evolving matrix sequence.
published_or_final_version
Computer Science
Doctoral
Doctor of Philosophy
APA, Harvard, Vancouver, ISO, and other styles
10

King, David Jonathan. "Functional programming and graph algorithms." Thesis, University of Glasgow, 1996. http://theses.gla.ac.uk/1629/.

Full text
Abstract:
This thesis is an investigation of graph algorithms in the non-strict purely functional language Haskell. Emphasis is placed on the importance of achieving an asymptotic complexity as good as with conventional languages. This is achieved by using the monadic model for including actions on the state. Work on the monadic model was carried out at Glasgow University by Wadler, Peyton Jones, and Launchbury in the early nineties and has opened up many diverse application areas. One area is the ability to express data structures that require sharing. Although graphs are not presented in this style, data structures that graph algorithms use are expressed in this style. Several examples of stateful algorithms are given including union/find for disjoint sets, and the linear time sort binsort. The graph algorithms presented are not new, but are traditional algorithms recast in a functional setting. Examples include strongly connected components, biconnected components, Kruskal's minimum cost spanning tree, and Dijkstra's shortest paths. The presentation is lucid giving more insight than usual. The functional setting allows for complete calculational style correctness proofs - which is demonstrated with many examples. The benefits of using a functional language for expressing graph algorithms are quantified by looking at the issues of execution times, asymptotic complexity, correctness, and clarity, in comparison with traditional approaches. The intention is to be as objective as possible, pointing out both the weaknesses and the strengths of using a functional language.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Graph algorithms"

1

Even, Shimon. Graph algorithms. 2nd ed. Cambridge, NY: Cambridge University Press, 2011.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Erciyes, K. Algebraic Graph Algorithms. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-87886-3.

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

Baggenstos, Daniel. Graph isomorphism algorithms. Saarbrücken: VDM Verlag, 2008.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

1960-, Tamassia Roberto, and Tollis Ioannis G. 1958-, eds. Graph algorithms and applications I. River Edge, N.J: World Scientific, 2002.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

Erciyes, K. Guide to Graph Algorithms. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-73235-0.

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

Evstigneev, V. A. Teorii͡a︡ grafov: Algoritmy obrabotki beskonturnykh grafov. Novosibirsk: "Nauka," Sibirskoe predprii͡a︡tie RAN, 1998.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

1957-, Gutin Gregory, ed. Digraphs: Theory, algorithms, and applications. 2nd ed. London: Springer, 2009.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

1957-, Gutin Gregory, ed. Digraphs: Theory, algorithms, and applications. London: Springer, 2001.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
9

Giuseppe, Di Battista, ed. Graph drawing: Algorithms for the visualization of graphs. Upper Saddle River, N.J: Prentice Hall, 1999.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
10

Toshihide, Ibaraki, ed. Algorithmic aspects of graph connectivity. New York: Cambridge University Press, 2008.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Graph algorithms"

1

Izadkhah, Habib. "Graph." In Problems on Algorithms, 471–85. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-17043-0_13.

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

Peng, Sheng-Lung, Ming-Tat Ko, Chin-Wen Ho, Tsan-sheng Hsu, and Chuan-Yi Tang. "Graph searching on chordal graphs." In Algorithms and Computation, 156–65. Berlin, Heidelberg: Springer Berlin Heidelberg, 1996. http://dx.doi.org/10.1007/bfb0009491.

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

Hetland, Magnus Lie. "Graph Terminology." In Python Algorithms, 267–71. Berkeley, CA: Apress, 2014. http://dx.doi.org/10.1007/978-1-4842-0055-1_14.

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

Adamson, Iain T. "Graph Algorithms." In Data Structures and Algorithms: A First Course, 171–213. London: Springer London, 1996. http://dx.doi.org/10.1007/978-1-4471-1023-1_8.

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

Karimov, Elshad. "Graph Algorithms." In Data Structures and Algorithms in Swift, 163–94. Berkeley, CA: Apress, 2020. http://dx.doi.org/10.1007/978-1-4842-5769-2_16.

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

Dally, William J. "Graph Algorithms." In The Kluwer International Series in Engineering and Computer Science, 75–132. Boston, MA: Springer US, 1987. http://dx.doi.org/10.1007/978-1-4613-1995-5_4.

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

Laaksonen, Antti. "Graph Algorithms." In Undergraduate Topics in Computer Science, 77–106. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-72547-5_7.

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

Laaksonen, Antti. "Graph Algorithms." In Undergraduate Topics in Computer Science, 83–113. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-39357-1_7.

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

Shen, Alexander. "Graph algorithms." In Algorithms and Programming, 124–32. Boston, MA: Birkhäuser Boston, 1997. http://dx.doi.org/10.1007/978-0-8176-4761-2_9.

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

Lengauer, Thomas. "Graph Algorithms." In Combinatorial Algorithms for Integrated Circuit Layout, 47–135. Wiesbaden: Vieweg+Teubner Verlag, 1990. http://dx.doi.org/10.1007/978-3-322-92106-2_3.

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

Conference papers on the topic "Graph algorithms"

1

Klobas, Nina, and Matjaž Krnc. "Fast Recognition of Some Parametric Graph Families." In 7th Student Computer Science Research Conference. University of Maribor Press, 2021. http://dx.doi.org/10.18690/978-961-286-516-0.7.

Full text
Abstract:
Recognizing graphs with high level of symmetries is hard in general, and usually requires additional structural understanding. In this paper we study a particular graph parameter and motivate its usage by devising eÿcient recognition algorithm for the family of I-graphs. For integers m a simple graph is cycle regular if every path of length ` belongs to exactly cycles of length m. We identify all cycle regular I-graphs and, as a conse-quence, describe linear recognition algorithm for the observed family. Similar procedure can be used to devise the recog-nition algorithms for Double generalized Petersen graphs and folded cubes. Besides that, we believe the structural observations and methods used in the paper are of independent interest and could be used for solving other algorithmic problems.
APA, Harvard, Vancouver, ISO, and other styles
2

Pucheta, Martín A., Nicolás E. Ulrich, and Alberto Cardona. "Combined Graph Layout Algorithms for Automated Sketching of Kinematic Chains." In ASME 2012 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2012. http://dx.doi.org/10.1115/detc2012-70665.

Full text
Abstract:
The graph layout problem arises frequently in the conceptual stage of mechanism design, specially in the enumeration process where a large number of topological solutions must be analyzed. Two main objectives of graph layout are the avoidance or minimization of edge crossings and the aesthetics. Edge crossings cannot be always avoided by force-directed algorithms since they reach a minimum of the energy in dependence with the initial position of the vertices, often randomly generated. Combinatorial algorithms based on the properties of the graph representation of the kinematic chain can be used to find an adequate initial position of the vertices with minimal edge crossings. To select an initial layout, the minimal independent loops of the graph can be drawn as circles followed by arcs, in all forms. The computational cost of this algorithm grows as factorial with the number of independent loops. This paper presents a combination of two algorithms: a combinatorial algorithm followed by a force-directed algorithm based on spring repulsion and electrical attraction, including a new concept of vertex-to-edge repulsion to improve aesthetics and minimize crossings. Atlases of graphs of complex kinematic chains are used to validate the results. The layouts obtained have good quality in terms of minimization of edge crossings and maximization of aesthetic characteristics.
APA, Harvard, Vancouver, ISO, and other styles
3

Pan, Shirui, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. "Adversarially Regularized Graph Autoencoder for Graph Embedding." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/362.

Full text
Abstract:
Graph embedding is an effective method to represent graph data in a low dimensional space for graph analytics. Most existing embedding algorithms typically focus on preserving the topological structure or minimizing the reconstruction errors of graph data, but they have mostly ignored the data distribution of the latent codes from the graphs, which often results in inferior embedding in real-world graph data. In this paper, we propose a novel adversarial graph embedding framework for graph data. The framework encodes the topological structure and node content in a graph to a compact representation, on which a decoder is trained to reconstruct the graph structure. Furthermore, the latent representation is enforced to match a prior distribution via an adversarial training scheme. To learn a robust embedding, two variants of adversarial approaches, adversarially regularized graph autoencoder (ARGA) and adversarially regularized variational graph autoencoder (ARVGA), are developed. Experimental studies on real-world graphs validate our design and demonstrate that our algorithms outperform baselines by a wide margin in link prediction, graph clustering, and graph visualization tasks.
APA, Harvard, Vancouver, ISO, and other styles
4

Stanton, Isabelle. "Streaming Balanced Graph Partitioning Algorithms for Random Graphs." In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2013. http://dx.doi.org/10.1137/1.9781611973402.95.

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

Mariano, Matheus Monteiro, Érica Ferreira Souza, André Takeshi Endo, and Nandamudi L. Vijaykumar. "A comparative study of algorithms for generating switch cover test sets." In XV Simpósio Brasileiro de Qualidade de Software. Sociedade Brasileira de Computação - SBC, 2016. http://dx.doi.org/10.5753/sbqs.2016.15122.

Full text
Abstract:
Test case generation based on Finite State Machines (FSMs) has been extensively investigated due to its accuracy and simplicity. Several test criteria have been proposed in the literature to generate test cases based on FSMs. One of the oldest criteria is the Switch Cover. As a main feature, the Switch Cover criterion defines that all transition pairs of an FSM must be covered. The classical Switch Cover algorithm converts the FSM into a graph (known as Dual Graph); this graph is balanced, and, finally, traversed based on an Eulerian Cycle algorithm. In this context, considering the stage where an FSM is converted into a graph, this study investigates other search algorithms on graphs, namely Depth-First Search (DFS) and Breadth-First Search (BFS), for generating test sets from a Dual Graph. We presented an experimental study that compares the DFS, BFS algorithms with the Eulerian Cycle. The study was conducted with a set of random and real-world machines, taking into account the number of test cases, the test suite size, the average length of sequences and generation time.
APA, Harvard, Vancouver, ISO, and other styles
6

BABAI, LÁSZLÓ. "GROUP, GRAPHS, ALGORITHMS: THE GRAPH ISOMORPHISM PROBLEM." In International Congress of Mathematicians 2018. WORLD SCIENTIFIC, 2019. http://dx.doi.org/10.1142/9789813272880_0183.

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

Wang, Chun, Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, and Chengqi Zhang. "Attributed Graph Clustering: A Deep Attentional Embedding Approach." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/509.

Full text
Abstract:
Graph clustering is a fundamental task which discovers communities or groups in networks. Recent studies have mostly focused on developing deep learning approaches to learn a compact graph embedding, upon which classic clustering methods like k-means or spectral clustering algorithms are applied. These two-step frameworks are difficult to manipulate and usually lead to suboptimal performance, mainly because the graph embedding is not goal-directed, i.e., designed for the specific clustering task. In this paper, we propose a goal-directed deep learning approach, Deep Attentional Embedded Graph Clustering (DAEGC for short). Our method focuses on attributed graphs to sufficiently explore the two sides of information in graphs. By employing an attention network to capture the importance of the neighboring nodes to a target node, our DAEGC algorithm encodes the topological structure and node content in a graph to a compact representation, on which an inner product decoder is trained to reconstruct the graph structure. Furthermore, soft labels from the graph embedding itself are generated to supervise a self-training graph clustering process, which iteratively refines the clustering results. The self-training process is jointly learned and optimized with the graph embedding in a unified framework, to mutually benefit both components. Experimental results compared with state-of-the-art algorithms demonstrate the superiority of our method.
APA, Harvard, Vancouver, ISO, and other styles
8

Fan, Wenfei, Chao Tian, Ruiqi Xu, Qiang Yin, Wenyuan Yu, and Jingren Zhou. "Incrementalizing Graph Algorithms." In SIGMOD/PODS '21: International Conference on Management of Data. New York, NY, USA: ACM, 2021. http://dx.doi.org/10.1145/3448016.3452796.

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

Kay, Bill, Prasanna Date, and Catherine Schuman. "Neuromorphic Graph Algorithms." In NICE '20: Neuro-inspired Computational Elements Workshop. New York, NY, USA: ACM, 2020. http://dx.doi.org/10.1145/3381755.3381762.

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

Kaur, Jasmeet, and Nathan R. Sturtevant. "Efficient Budgeted Graph Search." In Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. California: International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/660.

Full text
Abstract:
Iterative Budgeted Exponential Search (IBEX) is a general search algorithm that can limit the number of re-expansions performed in common problems like iterative-deepening tree search and search with inconsistent heuristics. IBEX has been adapted into a specific tree algorithm, Budgeted Tree Search (BTS), which behaves like IDA* when the problem instance is well-behaved but keeps the worst-case guarantees when problems are not well-behaved. The analogous algorithms on graphs, Budgeted Graph Search (BGS), do not have these same properties. This paper reformulates BGS into Efficient Budgeted Graph Search (BGSe), showing how to implement the algorithm so that it behaves identically to A* when problems are well-behaved, and retains the best-case performance otherwise. Experimental results validate the performance of BGSe on a range of theoretical and practical problem instances.
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Graph algorithms"

1

Parekh, Ojas, Yipu Wang, Yang Ho, Cynthia Phillips, Ali Pinar, James Aimone, and William Severa. Neuromorphic Graph Algorithms. Office of Scientific and Technical Information (OSTI), November 2021. http://dx.doi.org/10.2172/1829422.

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

Werner, Eric, and Jonathan Chu. Graph Algorithms on Future Architectures. Fort Belvoir, VA: Defense Technical Information Center, October 2014. http://dx.doi.org/10.21236/ada611678.

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

McLendon, William Clarence, III, and Brian Neil Wylie. Graph algorithms in the titan toolkit. Office of Scientific and Technical Information (OSTI), October 2009. http://dx.doi.org/10.2172/1001014.

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

GEORGIA INST OF TECH ATLANTA. Graph Minors: Structure Theory and Algorithms. Fort Belvoir, VA: Defense Technical Information Center, April 1993. http://dx.doi.org/10.21236/ada266033.

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

Thomas, Robin. Graph Minors: Structure Theory and Algorithms. Fort Belvoir, VA: Defense Technical Information Center, January 1993. http://dx.doi.org/10.21236/ada271851.

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

Plotkin, Serge. Research in Graph Algorithms and Combinatorial Optimization. Fort Belvoir, VA: Defense Technical Information Center, March 1995. http://dx.doi.org/10.21236/ada292630.

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

Sullivan, Blair D., Dinesh P. Weerapurage, and Christopher S. Groer. Parallel Algorithms for Graph Optimization using Tree Decompositions. Office of Scientific and Technical Information (OSTI), June 2012. http://dx.doi.org/10.2172/1042920.

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

Gabow, Harold N., and Robert E. Tarjan. Faster Scaling Algorithms for General Graph Matching Problems. Fort Belvoir, VA: Defense Technical Information Center, April 1989. http://dx.doi.org/10.21236/ada215112.

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

Ja'Ja, Joseph, and S. R. Kosaraju. Parallel Algorithms for Planar Graph. Isomorphism and Related Problems. Fort Belvoir, VA: Defense Technical Information Center, January 1986. http://dx.doi.org/10.21236/ada444434.

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

Taha, Mohammad. Memristive Architectures and Algorithms for Approximate Graph-based Inference. Portland State University Library, January 2000. http://dx.doi.org/10.15760/etd.7391.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Graph algorithms' for particular source types:
Journal articles Dissertations / Theses 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