Relevant bibliographies by topics / Graph algorithmics

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature on the topic 'Graph algorithmics'

Author: Grafiati
Published: 14 December 2024

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

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Graph algorithmics.'

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 algorithmics"

1

Meyer, Ulrich, and Manuel Penschuck. "Large-scale graph generation: Recent results of the SPP 1736 – Part II." it - Information Technology 62, no. 3-4 (May 27, 2020): 135–44. http://dx.doi.org/10.1515/itit-2019-0041.

Full text
Abstract:
AbstractThe selection of input data is a crucial step in virtually every empirical study. Experimental campaigns in algorithm engineering, experimental algorithmics, network analysis, and many other fields often require suited network data. In this context, synthetic graphs play an important role, as data sets of observed networks are typically scarce, biased, not sufficiently understood, and may pose logistic and legal challenges. Just like processing huge graphs becomes challenging in the big data setting, new algorithmic approaches are necessary to generate such massive instances efficiently. Here, we update our previous survey [35] on results for large-scale graph generation obtained within the DFG priority programme SPP 1736 (Algorithms for Big Data); to this end, we broaden the scope and include recently published results.
APA, Harvard, Vancouver, ISO, and other styles
2

Mihelič, Jurij, and Uroš Čibej. "An experimental evaluation of refinement techniques for the subgraph isomorphism backtracking algorithms." Open Computer Science 11, no. 1 (December 17, 2020): 33–42. http://dx.doi.org/10.1515/comp-2020-0149.

Full text
Abstract:
AbstractIn this paper, we study a well-known computationally hard problem, called the subgraph isomorphism problem where the goal is for a given pattern and target graphs to determine whether the pattern is a subgraph of the target graph. Numerous algorithms for solving the problem exist in the literature and most of them are based on the backtracking approach. Since straightforward backtracking is usually slow, many algorithmic refinement techniques are used in practical algorithms. The main goal of this paper is to study such refinement techniques and to determine their ability to speed up backtracking algorithms. To do this we use a methodology of experimental algorithmics. We perform an experimental evaluation of the techniques and their combinations and, hence, demonstrate their usefulness in practice.
APA, Harvard, Vancouver, ISO, and other styles
3

Reddy, K. Krishna Mohan, P. Renjith, and N. Sadagopan. "Listing all spanning trees in Halin graphs — sequential and Parallel view." Discrete Mathematics, Algorithms and Applications 10, no. 01 (February 2018): 1850005. http://dx.doi.org/10.1142/s1793830918500052.

Full text
Abstract:
For a connected labeled graph [Formula: see text], a spanning tree [Formula: see text] is a connected and acyclic subgraph that spans all vertices of [Formula: see text]. In this paper, we consider a classical combinatorial problem which is to list all spanning trees of [Formula: see text]. A Halin graph is a graph obtained from a tree with no degree two vertices and by joining all leaves with a cycle. We present a sequential and parallel algorithm to enumerate all spanning trees in Halin graphs. Our approach enumerates without repetitions and we make use of [Formula: see text] processors for parallel algorithmics, where [Formula: see text] and [Formula: see text] are the depth, the number of leaves, respectively, of the Halin graph. We also prove that the number of spanning trees in Halin graphs is [Formula: see text].
APA, Harvard, Vancouver, ISO, and other styles
4

Bentert, Matthias, Leon Kellerhals, and Rolf Niedermeier. "Fair Short Paths in Vertex-Colored Graphs." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 10 (June 26, 2023): 12346–54. http://dx.doi.org/10.1609/aaai.v37i10.26455.

Full text
Abstract:
The computation of short paths in graphs with arc lengths is a pillar of graph algorithmics and network science. In a more diverse world, however, not every short path is equally valuable. For the setting where each vertex is assigned to a group (color), we provide a framework to model multiple natural fairness aspects. We seek to find short paths in which the number of occurrences of each color is within some given lower and upper bounds. Among other results, we prove the introduced problems to be computationally intractable (NP-hard and parameterized hard with respect to the number of colors) even in very restricted settings (such as each color should appear with exactly the same frequency), while also presenting an encouraging algorithmic result ("fixed-parameter tractability") related to the length of the sought solution path for the general problem.
APA, Harvard, Vancouver, ISO, and other styles
5

Casteigts, Arnaud, Anne-Sophie Himmel, Hendrik Molter, and Philipp Zschoche. "Finding Temporal Paths Under Waiting Time Constraints." Algorithmica 83, no. 9 (June 4, 2021): 2754–802. http://dx.doi.org/10.1007/s00453-021-00831-w.

Full text
Abstract:
AbstractComputing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or temporal, if it uses edges with non-decreasing time stamps. We investigate a basic constraint for temporal paths, where the time spent at each vertex must not exceed a given duration $$\varDelta $$ Δ , referred to as $$\varDelta $$ Δ -restless temporal paths. This constraint arises naturally in the modeling of real-world processes like packet routing in communication networks and infection transmission routes of diseases where recovery confers lasting resistance. While finding temporal paths without waiting time restrictions is known to be doable in polynomial time, we show that the “restless variant” of this problem becomes computationally hard even in very restrictive settings. For example, it is W[1]-hard when parameterized by the distance to disjoint path of the underlying graph, which implies W[1]-hardness for many other parameters like feedback vertex number and pathwidth. A natural question is thus whether the problem becomes tractable in some natural settings. We explore several natural parameterizations, presenting FPT algorithms for three kinds of parameters: (1) output-related parameters (here, the maximum length of the path), (2) classical parameters applied to the underlying graph (e.g., feedback edge number), and (3) a new parameter called timed feedback vertex number, which captures finer-grained temporal features of the input temporal graph, and which may be of interest beyond this work.
APA, Harvard, Vancouver, ISO, and other styles
6

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
7

Cappelletti, Luca, Tommaso Fontana, Elena Casiraghi, Vida Ravanmehr, Tiffany J. Callahan, Carlos Cano, Marcin P. Joachimiak, et al. "GRAPE for fast and scalable graph processing and random-walk-based embedding." Nature Computational Science 3, no. 6 (June 26, 2023): 552–68. http://dx.doi.org/10.1038/s43588-023-00465-8.

Full text
Abstract:
AbstractGraph representation learning methods opened new avenues for addressing complex, real-world problems represented by graphs. However, many graphs used in these applications comprise millions of nodes and billions of edges and are beyond the capabilities of current methods and software implementations. We present GRAPE (Graph Representation Learning, Prediction and Evaluation), a software resource for graph processing and embedding that is able to scale with big graphs by using specialized and smart data structures, algorithms, and a fast parallel implementation of random-walk-based methods. Compared with state-of-the-art software resources, GRAPE shows an improvement of orders of magnitude in empirical space and time complexity, as well as competitive edge- and node-label prediction performance. GRAPE comprises approximately 1.7 million well-documented lines of Python and Rust code and provides 69 node-embedding methods, 25 inference models, a collection of efficient graph-processing utilities, and over 80,000 graphs from the literature and other sources. Standardized interfaces allow a seamless integration of third-party libraries, while ready-to-use and modular pipelines permit an easy-to-use evaluation of graph-representation-learning methods, therefore also positioning GRAPE as a software resource that performs a fair comparison between methods and libraries for graph processing and embedding.
APA, Harvard, Vancouver, ISO, and other styles
8

Ergenç Bostanoğlu, Belgin, and Nourhan Abuzayed. "Dynamic frequent subgraph mining algorithms over evolving graphs: a survey." PeerJ Computer Science 10 (October 8, 2024): e2361. http://dx.doi.org/10.7717/peerj-cs.2361.

Full text
Abstract:
Frequent subgraph mining (FSM) is an essential and challenging graph mining task used in several applications of the modern data science. Some of the FSM algorithms have the objective of finding all frequent subgraphs whereas some of the algorithms focus on discovering frequent subgraphs approximately. On the other hand, modern applications employ evolving graphs where the increments are small graphs or stream of nodes and edges. In such cases, FSM task becomes more challenging due to growing data size and complexity of the base algorithms. Recently we see frequent subgraph mining algorithms designed for dynamic graph data. However, there is no comparative review of the dynamic subgraph mining algorithms focusing on the discovery of frequent subgraphs over evolving graph data. This article focuses on the characteristics of dynamic frequent subgraph mining algorithms over evolving graphs. We first introduce and compare dynamic frequent subgraph mining algorithms; trying to highlight their attributes as increment type, graph type, graph representation, internal data structure, algorithmic approach, programming approach, base algorithm and output type. Secondly, we introduce and compare the approximate frequent subgraph mining algorithms for dynamic graphs with additional attributes as their sampling strategy, data in the sample, statistical guarantees on the sample and their main objective. Finally, we highlight research opportunities in this specific domain from our perspective. Overall, we aim to introduce the research area of frequent subgraph mining over evolving graphs with the hope that this can serve as a reference and inspiration for the researchers of the field.
APA, Harvard, Vancouver, ISO, and other styles
9

Nikolopoulos, Stavros D., and Leonidas Palios. "Parallel Algorithms for Recognizing P5-free and ${\bar P}_5$-free Weakly Chordal Graphs." Parallel Processing Letters 14, no. 01 (March 2004): 119–29. http://dx.doi.org/10.1142/s0129626404001763.

Full text
Abstract:
We prove algorithmic characterizations of weakly chordal graphs, which lead to efficient parallel algorithms for recognizing P5-free and [Formula: see text]-free weakly chordal graphs. For an input graph on n vertices and m edges, our algorithms run in O( log 2n) time and require O(m2/ log n) processors on the EREW PRAM model of computation. The proposed recognition algorithms efficiently detect P5 s and [Formula: see text] in weakly chordal graphs in O( log n) time with O(m2/ log n) processors on the EREW PRAM. Additionally, we show how the algorithms can be augmented to provide a certificate for the existence of a P5 (or a [Formula: see text]) in case the input graph is not P5-free (respectively, [Formula: see text]-free) weakly chordal.
APA, Harvard, Vancouver, ISO, and other styles
10

KHOUSSAINOV, BAKHADYR, JIAMOU LIU, and MIA MINNES. "Unary automatic graphs: an algorithmic perspective." Mathematical Structures in Computer Science 19, no. 1 (February 2009): 133–52. http://dx.doi.org/10.1017/s0960129508007342.

Full text
Abstract:
This paper studies infinite graphs produced from a natural unfolding operation applied to finite graphs. Graphs produced using such operations are of finite degree and automatic over the unary alphabet (that is, they can be described by finite automata over the unary alphabet). We investigate algorithmic properties of such unfolded graphs given their finite presentations. In particular, we ask whether a given node belongs to an infinite component, whether two given nodes in the graph are reachable from one another and whether the graph is connected. We give polynomial-time algorithms for each of these questions. For a fixed input graph, the algorithm for the first question is in constant time and the second question is decided using an automaton that recognises the reachability relation in a uniform way. Hence, we improve on previous work, in which non-elementary or non-uniform algorithms were found.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Graph algorithmics"

1

Pitois, François. "Recherche de régularités et représentations succinctes de graphes." Electronic Thesis or Diss., Bourgogne Franche-Comté, 2024. http://www.theses.fr/2024UBFCK021.

Full text
Abstract:
Dans cette thèse, nous étudions les régularités dans les graphes et les représentations succinctes des graphes. Une régularité, ou structure, est un terme générique qui désigne un ensemble de sommets du graphe ayant certaines propriétés. Parmi les régularités les plus connues, nous pouvons citer les cliques, les sous-graphes denses, les communautés, les modules et les splits. Une représentation succincte d'un graphe est une façon de le décrire qui est plus efficace que de simplement lister les différentes arêtes du graphe. Chercher des régularités permet d'obtenir des représentations succinctes. Ainsi, dans un premier temps, nous avons développé un algorithme de compression de graphe qui cherche différentes régularités du graphe, en sélectionne une partie et partitionne le graphe en fonction des structures sélectionnées. Cet algorithme donne une description succincte du graphe qui est meilleure que certains algorithmes de référence.Dans un deuxième temps, nous avons créé nos propres structures, de sorte qu'elles soient adaptées à la compression et qu'elles soient assez facile à chercher. Pour ce faire, nous sommes partis d'une structure connue, le split, et nous l'avons généralisée en créant le r-split, où r est un paramètre entier fixé. Nous avons alors montré que l'ensemble des r-splits d'un graphe a une cohérence globale, dans le sens où seul un nombre polynomial d'entre eux suffit à décrire l'intégralité des r-splits du graphe. Cela généralise une propriété bien connue des splits, pour lesquels seul un nombre linéaire d'entre eux suffit à retrouver tous les autres. Nous avons également montré que les r-splits peuvent se calculer en temps polynomial en utilisant des algorithmes d'optimisation de fonctions sous-modulaires.Dans un troisième temps, nous nous sommes intéressés à la recherche de structures particulières : les motifs dans les graphes ordonnés. Un graphe ordonné est un graphe dans lequel les sommets sont ordonnés de 1 à n. Un motif est un sous-graphe ordonné partiel, dans le sens où chaque paire de sommets peut être reliée soit par une arête, soit par une non-arête, soit par ni l'une ni l'autre. Le but est de fixer un motif P et de construire un algorithme capable de détecter si P est dans n'importe quel graphe ordonné donné en paramètre. Ce problème est polynomial en la taille du graphe via une recherche exhaustive. Cependant, est-il possible de faire mieux ? Nous avons montré que oui : la plupart des motifs à trois sommets peuvent être détectés en temps linéaire là où une recherche exhaustive nécessite un temps cubique. Concernant les motifs plus grands, nous avons exhibé des classes de motifs qui peuvent être détectés en temps sous-cubique : les motifs planaires extérieurs. En ajoutant des contraintes supplémentaires, nous avons exhibé une classe de motifs qui peuvent être détectée en temps linéaire : il s'agit des motifs planaires extérieurs sans cycle et sans non-arête
In this thesis, we investigate regularities in graphs and succinct representations of graphs.A regularity, or structure, is a generic term that refers to a set of vertices in a graph with certain properties.Among the most well-known regularities, we can mention cliques, dense subgraphs, communities, modules, and splits.A succinct representation of a graph is a way of describing it that is more efficient than simply listing the different edges of the graph.Searching for regularities enables obtaining succinct representations.Thus, in a first step, we developed a graph compression algorithm that searches for different graph regularities, selects a portion of them, and partitions the graph based on the selected structures.This algorithm provides a succinct description of the graph that is better than some benchmark algorithms.In a second step, we created our own structures, so they are suitable for compression and are easy enough to search for.To do this, we started from a known structure, the split, and generalized it to create the r-split, where r is a fixed integer parameter.We then showed that the set of r-splits of a graph has a global coherence, in the sense that only a polynomial number of them is sufficient to describe all r-splits of the graph.This generalizes a well-known property of splits, for which only a linear number of them is sufficient to recover all the others.We also demonstrated that r-splits can be computed in polynomial time using submodular function optimization algorithms.In a third step, we focused on searching for particular regularities: patterns in ordered graphs.An ordered graph is a graph in which the vertices are ordered from 1 to n.A pattern is a partial ordered subgraph, in the sense that each pair of vertices can be connected either by an edge, a non-edge, or neither.The goal is to fix a pattern P and build an algorithm capable of detecting if P is in any ordered graph given as an input.This problem is polynomial in the size of the graph via exhaustive search.However, is it possible to do better?We were able to show that yes: most three-vertex patterns can be detected in linear time while exhaustive search requires cubic time.Regarding larger patterns, we exhibited classes of patterns that can be detected in subcubic time: outerplanar patterns.By adding additional constraints, we exhibited a class of patterns that can be detected in linear time: these are outerplanar patterns without cycles and non-edges
APA, Harvard, Vancouver, ISO, and other styles
2

Dusart, Jérémie. "Graph searches with applications to cocomparability graphs." Paris 7, 2014. http://www.theses.fr/2014PA077048.

Full text
Abstract:
Un parcours de graphe est un mécanisme pour visiter de manière itérative les sommets d'un graphe. Cela a été une technique fondamentale dans la conception des algorithmes de graphe depuis les débuts de l'informatique. Bon nombre des premiers parcours étaient basées sur le parcours en largeur(BFS) ou en profondeur (DFS) et cela a donné des algorithmes efficaces pour les problèmes pratiques tels que la distance entre deux sommets, le diamètre, la connectivité, les problèmes de flot et la reconnaissance des graphes planaires. Le but de cette thèse est d'étudier les parcours de graphe Dans cette thèse, nous présentons des résultats généraux sur les parcours de graphe dans les graphes de cocomparabilité, mais aussi une nouvelle caractérisation des graphes de cocomparabilité et des applications des parcours de graphe pour résoudre le problème d'orientation transitive, de sous-graphe triangulé maximal, de clique séparatrice et de sommets simpliciaux. Un modèle simple et général est aussi présenté pour capturer la plupart des parcours de graphe
A graph search is a mechanism for systematically visiting the vertices of a graph. It has been a fundamental technique in the design of graph algorithms since the eraarly days of computer science. Many of the early search methods were based on Breadth First Search (BFS) or Depth First Search (DFS) and resulted in efficient algorithms for practical problems such as the distance between two vertices, diameter, connectivity, network flows and the recognition of planar graphs. The purpose of this thesis is to studied the graph search. In this thesis, we present general result about graph search in cocomparability grapj, but also a new charactrization of cocomparability graph and apllications of graph search to solve the problem of transitive orientation, maximal chordal subgraph, clique perator and simplicial vertices. A simple and general framework is also presented to capture most of the well known graph search
APA, Harvard, Vancouver, ISO, and other styles
3

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
4

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
5

Dinh, Trong Hiêu. "Grammaires de graphes et langages formels." Phd thesis, Université Paris-Est, 2011. http://tel.archives-ouvertes.fr/tel-00665732.

Full text
Abstract:
Cette thèse apporte plusieurs contributions dans le domaine des langages formels. Notre premier travail a été de montrer la pertinence des grammaires de graphes comme outil de démonstration de résultats fondamentaux sur les langages algébriques. Nous avons ainsi reformulé avec un point de vue géométrique les démonstrations du lemme des paires itérantes et du lemme de Parikh. Nous avons ensuite étendu aux graphes réguliers des algorithmes de base sur les graphes finis, notamment pour calculer des problèmes de plus court chemin. Ces extensions ont été faites par calcul de plus petits points fixes sur les grammaires de graphes. Enfin, nous avons caractérisé des familles générales de systèmes de récriture de mots dont la dérivation préserve la régularité ou l'algébricité. Ces familles ont été obtenues par décomposition de la dérivation en une substitution régulière suivie de la dérivation du système de Dyck
APA, Harvard, Vancouver, ISO, and other styles
6

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 text
Abstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011.
Cataloged 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.
APA, Harvard, Vancouver, ISO, and other styles
7

Duffy, Christopher. "Homomorphisms of (j, k)-mixed graphs." Thesis, Bordeaux, 2015. http://hdl.handle.net/1828/6601.

Full text
Abstract:
A mixed graph is a simple graph in which a subset of the edges have been assigned directions to form arcs. For non-negative integers j and k, a (j, k)−mixed graph is a mixed graph with j types of arcs and k types of edges. The collection of (j, k)−mixed graphs contains simple graphs ((0,1)−mixed graphs), oriented graphs ((1,0)-mixed graphs) and k−edge-coloured graphs ((0, k)−mixed graphs). A homomorphism is a vertex mapping from one (j,k)−mixed graph to another in which edge type is preserved, and arc type and direction are preserved. An m−colouring of a (j, k)−mixed graph is a homomorphism from that graph to a target with m vertices. The (j, k)−chromatic number of a (j, k)−mixed graph is the least m such that an m−colouring exists. When (j, k) = (0, 1), we see that these definitions are consistent with the usual definitions of graph homomorphism and graph colouring. Similarly, when (j, k) = (1, 0) and (j, k) = (0, k) these definitions are consistent with the usual definitions of homomorphism and colouring for oriented graphs and k−edge-coloured graphs, respectively. In this thesis we study the (j, k)−chromatic number and related parameters for different families of graphs, focussing particularly on the (1, 0)−chromatic number, more commonly called the oriented chromatic number, and the (0, k)−chromatic number. In examining oriented graphs, we provide improvements to the upper and lower bounds for the oriented chromatic number of the families of oriented graphs with maximum degree 3 and 4. We generalise the work of Sherk and MacGillivray on the 2−dipath chromatic number, to consider colourings in which vertices at the ends of iii a directed path of length at most k must receive different colours. We examine the implications of the work of Smolikova on simple colourings to study of the oriented chromatic number of the family of oriented planar graphs. In examining k−edge-coloured graphs we provide improvements to the upper and lower bounds for the family of 2−edge-coloured graphs with maximum degree 3. In doing so, we define the alternating 2−path chromatic number of k−edge-coloured graphs, a parameter similar in spirit to the 2−dipath chromatic number for oriented graphs. We also consider a notion of simple colouring for k−edge-coloured graphs, and show that the methods employed by Smolikova ́ for simple colourings of oriented graphs may be adapted to k−edge-coloured graphs. In addition to considering vertex colourings, we also consider incidence colourings of both graphs and digraphs. Using systems of distinct representatives, we provide a new characterisation of the incidence chromatic number. We define the oriented incidence chromatic number and find, by way of digraph homomorphism, a connection between the oriented incidence chromatic number and the chromatic number of the underlying graph. This connection motivates our study of the oriented incidence chromatic number of symmetric complete digraphs.
Graduate
APA, Harvard, Vancouver, ISO, and other styles
8

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
9

Sussfeld, Duncan. "Identifying remote homology and gene remodelling using network-based approaches." Electronic Thesis or Diss., université Paris-Saclay, 2024. http://www.theses.fr/2024UPASL112.

Full text
Abstract:
L'augmentation toujours plus importante de données génomiques et métagénomiques appelle de nouveaux développements méthodologiques et bio-informatiques, afin de caractériser avec davantage de précision les phénomènes évolutifs dans leur ensemble. En particulier, certaines des méthodes usuelles pour étudier l'évolution des (familles de) gènes s'avèrent inadaptées lorsque la parenté entre séquences n'est que partiellement supportée. Ainsi, la définition et la reconstruction de familles de gènes se heurtent à l'obstacle de l'homologie distante, qui passe sous le seuil de détection des alignements de séquences. De même, les mécanismes d'évolution combinatoire, tels que les fusions et fissions de gènes, remettent en cause les représentations purement arborescentes de l'évolution des familles de gènes. L'application de méthodes complémentaires basées sur les réseaux de similarité de séquences permet de contourner certaines de ces lacunes, en proposant une représentation holistique des similarités entre gènes. La détection et l'analyse d'homologues très divergents de familles de gènes fortement conservées dans des jeux de données environnementaux est notamment facilitée par la recherche itérative d'homologie fondée sur les réseaux. Cette fouille itérative de métagénomes révèle une immense diversité de variants environnementaux dans ces familles, qui divergent de la diversité connue tant par leur séquence que par la structure des protéines qu'ils encodent, et elle permet de suggérer des pistes pour guider de futures explorations de la matière noire microbienne. En outre, en prenant en compte des liens d'homologie partielle entre séquences génétiques, les réseaux de similarité de séquences permettent une identification systématique des évènements de fusion et de fission de gènes. Il devient ainsi possible d'évaluer l'impact de ces processus au cours de l'évolution de lignées biologiques d'intérêt, permettant de comparer le rôle qu'ils ont joué lors de l'émergence de phénotypes multicellulaires complexes dans plusieurs telles lignées. Plus généralement, ces approches basées sur les réseaux illustrent l'intérêt de prendre en compte une pluralité de modèles pour étudier une plus grande variété de processus évolutifs
The ever-increasing accumulation of genomic and metagenomic data calls for new methodological developments in bioinformatics, in order to characterise evolutionary phenomena as a whole with better accuracy. In particular, some of the canonical methods to study the evolution of genes and gene families may be ill-suited when the relatedness of sequences is only partially supported. For instance, the definition and reconstruction of gene families face the hurdle of remote homology, which falls beneath the detection thresholds of sequence alignments. Likewise, combinatorial mechanisms of evolution, such as gene fusion and gene fission, challenge the purely tree-based representations of gene family evolution. The use of complementary methods based on sequence similarity networks allows us to circumvent some of these shortcomings, by offering a more holistic representation of similarities between genes. The detection and analysis of highly divergent homologues of strongly conserved families in environmental sequence datasets, in particular, is facilitated by iterative homology search protocols based on networks. This iterative mining of metagenomes reveals an immense diversity of environmental variants in these families, diverging from the known diversity in primary sequence as well as in the tertiary structure of the proteins they encode. It is thus able to suggest possible directions of future explorations into microbial dark matter. Furthermore, by factoring in relationships of partial homology between gene sequences, sequence similarity networks allow for a systematic identification of gene fusion and fission events. It thus becomes possible to assess the effects of these processes on the evolution of biological lineages of interest, enabling us for instance to compare the role that they played in the emergence of complex multicellular phenotypes between several such lineages. More generally, these network-based approaches illustrate the benefits of taking a plurality of models into account, in order to study a broader range of evolutionary processes
APA, Harvard, Vancouver, ISO, and other styles
10

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
More sources

Books on the topic "Graph algorithmics"

1

Golumbic, Martin Charles. Algorithmic graph theory and perfect graphs. 2nd ed. Amsterdam: North Holland, 2004.

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

Golumbic, Martin Charles. Algorithmic graph theory and perfect graphs. Amsterdam: Elsevier, 2004.

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

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
4

Bonato, Anthony. The game of cops and robbers on graphs. Providence, R.I: American Mathematical Society, 2011.

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

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
6

Gdanskiy, Nikolay. Fundamentals of the theory and algorithms on graphs. ru: INFRA-M Academic Publishing LLC., 2020. http://dx.doi.org/10.12737/978686.

Full text
Abstract:
The textbook describes the main theoretical principles of graph theory, the main tasks to be solved using graph structures, and General methods of their solution and specific algorithms, with estimates of their complexity. I covered a lot of the examples given questions to test knowledge and tasks for independent decisions. Along with the control tasks to verify the theoretical training provided practical assignments to develop programs to study topics of graph theory. Meets the requirements of Federal state educational standards of higher education of the last generation. Designed for undergraduate and graduate programs, studying information technology, for in-depth training in analysis and design of systems of complex structure. Also the guide can be useful to specialists of the IT sphere in the study of algorithmic aspects of graph theory.
APA, Harvard, Vancouver, ISO, and other styles
7

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

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

McHugh, James A. Algorithmic graph theory. Englewood Cliffs, N.J: Prentice Hall, 1990.

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

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

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

Nagamochi, Hiroshi. 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 algorithmics"

1

Asahiro, Yuichi, Jesper Jansson, Eiji Miyano, Hirotaka Ono, and Sandhya T. P. "Graph Orientation with Edge Modifications." In Frontiers in Algorithmics, 38–50. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-18126-0_4.

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

Wang, Lusheng, Boting Yang, and Zhaohui Zhan. "Constrained Graph Searching on Trees." In Frontiers of Algorithmics, 239–51. Cham: Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-39344-0_18.

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

Zaroliagis, Christos D. "Implementations and Experimental Studies of Dynamic Graph Algorithms." In Experimental Algorithmics, 229–78. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/3-540-36383-1_11.

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

Fomin, Fedor V., Saket Saurabh, and Neeldhara Misra. "Graph Modification Problems: A Modern Perspective." In Frontiers in Algorithmics, 3–6. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-19647-3_1.

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

Vaishali, S., M. S. Atulya, and Nidhi Purohit. "Efficient Algorithms for a Graph Partitioning Problem." In Frontiers in Algorithmics, 29–42. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-78455-7_3.

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

Zou, Peng, Hui Li, Chunlin Xin, Wencheng Wang, and Binhai Zhu. "Finding Disjoint Dense Clubs in an Undirected Graph." In Frontiers in Algorithmics, 279–88. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-39817-4_27.

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

Abu-Khzam, Faisal N., Michael A. Langston, Amer E. Mouawad, and Clinton P. Nolan. "A Hybrid Graph Representation for Recursive Backtracking Algorithms." In Frontiers in Algorithmics, 136–47. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-14553-7_15.

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

Mertzios, George B., Othon Michail, George Skretas, Paul G. Spirakis, and Michail Theofilatos. "The Complexity of Growing a Graph." In Algorithmics of Wireless Networks, 123–37. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-22050-0_9.

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

Hanaka, Tesshu, Yasuaki Kobayashi, and Taiga Sone. "An Optimal Algorithm for Bisection for Bounded-Treewidth Graph." In Frontiers in Algorithmics, 25–36. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-59901-0_3.

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

Fürer, Martin. "Efficient Computation of the Characteristic Polynomial of a Threshold Graph." In Frontiers in Algorithmics, 45–51. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-19647-3_5.

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

Conference papers on the topic "Graph algorithmics"

1

Xie, Xinjiu, and Jinxian Zhang. "Link Prediction in Knowledge Graphs for Graph Convolutional Networks." In 2024 International Conference on Intelligent Algorithms for Computational Intelligence Systems (IACIS), 1–6. IEEE, 2024. http://dx.doi.org/10.1109/iacis61494.2024.10721627.

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

Lattanzi, Silvio, and Vahab Mirrokni. "Distributed Graph Algorithmics." In WSDM 2015: Eighth ACM International Conference on Web Search and Data Mining. New York, NY, USA: ACM, 2015. http://dx.doi.org/10.1145/2684822.2697043.

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

Shasha, Dennis, Jason T. L. Wang, and Rosalba Giugno. "Algorithmics and applications of tree and graph searching." In the twenty-first ACM SIGMOD-SIGACT-SIGART symposium. New York, New York, USA: ACM Press, 2002. http://dx.doi.org/10.1145/543613.543620.

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

Blum, Avrim, T.-H. Hubert Chan, and Mugizi Robert Rwebangira. "A Random-Surfer Web-Graph Model." In 2006 Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics (ANALCO). Philadelphia, PA: Society for Industrial and Applied Mathematics, 2006. http://dx.doi.org/10.1137/1.9781611972962.8.

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

Drmota, Michael, and Marc Noy. "Extremal Parameters in Sub-Critical Graph Classes." In 2013 Proceedings of the Tenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). Philadelphia, PA: Society for Industrial and Applied Mathematics, 2013. http://dx.doi.org/10.1137/1.9781611973037.1.

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

Jacquet, Philippe, and Abram Magner. "Variance of Size in Regular Graph Tries." In 2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). Philadelphia, PA: Society for Industrial and Applied Mathematics, 2014. http://dx.doi.org/10.1137/1.9781611973761.9.

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

Bóna, Miklós, and Andrew Vince. "The Number of Ways to Assemble a Graph." In 2013 Proceedings of the Tenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). Philadelphia, PA: Society for Industrial and Applied Mathematics, 2013. http://dx.doi.org/10.1137/1.9781611973037.2.

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

Zhao, Jun, and Panpan Zhang. "On Connectivity in a General Random Intersection Graph." In 2016 Proceedings of the Thirteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). Philadelphia, PA: Society for Industrial and Applied Mathematics, 2015. http://dx.doi.org/10.1137/1.9781611974324.12.

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

Nguyen, Van, and Chip Martel. "Augmented Graph Models for Small-World Analysis with Geographical Factors." In 2008 Proceedings of the Fifth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). Philadelphia, PA: Society for Industrial and Applied Mathematics, 2008. http://dx.doi.org/10.1137/1.9781611972986.5.

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

Whidden, Chris, and Frederick A. Matsen. "Ricci-Ollivier Curvature of the Rooted Phylogenetic Subtree-Prune-Regraft Graph." In 2016 Proceedings of the Thirteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). Philadelphia, PA: Society for Industrial and Applied Mathematics, 2015. http://dx.doi.org/10.1137/1.9781611974324.6.

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

Reports on the topic "Graph algorithmics"

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

Hrebeniuk, Bohdan V. Modification of the analytical gamma-algorithm for the flat layout of the graph. [б. в.], December 2018. http://dx.doi.org/10.31812/123456789/2882.

Full text
Abstract:
The planarity of graphs is one of the key sections of graph theory. Although a graph is an abstract mathematical object, most often it is graph visualization that makes it easier to study or develop in a particular area, for example, the infrastructure of a city, a company’s management or a website’s web page. In general, in the form of a graph, it is possible to depict any structures that have connections between the elements. But often such structures grow to such dimensions that it is difficult to determine whether it is possible to represent them on a plane without intersecting the bonds. There are many algorithms that solve this issue. One of these is the gamma method. The article identifies its problems and suggests methods for solving them, and also examines ways to achieve them.
APA, Harvard, Vancouver, ISO, and other styles
3

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
4

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
5

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
6

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
7

Gil, Oliver Fernández, and Anni-Yasmin Turhan. Answering Regular Path Queries Under Approximate Semantics in Lightweight Description Logics. Technische Universität Dresden, 2020. http://dx.doi.org/10.25368/2022.261.

Full text
Abstract:
Classical regular path queries (RPQs) can be too restrictive for some applications and answering such queries under approximate semantics to relax the query is desirable. While for answering regular path queries over graph databases under approximate semantics algorithms are available, such algorithms are scarce for the ontology-mediated setting. In this paper we extend an approach for answering RPQs over graph databases that uses weighted transducers to approximate paths from the query in two ways. The first extension is to answering approximate conjunctive 2-way regular path queries (C2RPQs) over graph databases and the second is to answering C2RPQs over ELH and DL-LiteR ontologies. We provide results on the computational complexity of the underlying reasoning problems and devise approximate query answering algorithms.
APA, Harvard, Vancouver, ISO, and other styles
8

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
9

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
10

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
You might also be interested in the extended bibliographies on the topic 'Graph algorithmics' 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