Relevant bibliographies by topics / Graph algorithmic

Academic literature on the topic 'Graph algorithmic'

Author: Grafiati
Published: 25 May 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 algorithmic.'

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

1

Möhring, Rolf H. "Algorithmic graph theory and perfect graphs." Order 3, no. 2 (June 1986): 207–8. http://dx.doi.org/10.1007/bf00390110.

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

Wilson, B. J. "ALGORITHMIC GRAPH THEORY." Bulletin of the London Mathematical Society 18, no. 6 (November 1986): 630–31. http://dx.doi.org/10.1112/blms/18.6.630.

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

Chen, Jianer. "Algorithmic graph embeddings." Theoretical Computer Science 181, no. 2 (July 1997): 247–66. http://dx.doi.org/10.1016/s0304-3975(96)00273-3.

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

de Werra, D. "Algorithmic graph theory." European Journal of Operational Research 26, no. 1 (July 1986): 179. http://dx.doi.org/10.1016/0377-2217(86)90177-3.

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

Lavrik, V. N. "Graph algorithmic algebra." Cybernetics 24, no. 5 (September 1988): 548–54. http://dx.doi.org/10.1007/bf01255666.

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

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
7

Bakonyi, Mihály, and Erik M. Varness. "Algorithmic aspects of bipartite graphs." International Journal of Mathematics and Mathematical Sciences 18, no. 2 (1995): 299–304. http://dx.doi.org/10.1155/s0161171295000378.

Full text
Abstract:
We generalize previous work done by Donald J. Rose and Robert E. Tarjan [2], who developed efficient algorithms for use on directed graphs. This paper considers an edge elimination process on bipartite graphs, presenting several theorems which lead to an algorithm for computing the minimal fill-in of a given ordered graph.
APA, Harvard, Vancouver, ISO, and other styles
8

Korpelainen, Nicholas, Vadim V. Lozin, Dmitriy S. Malyshev, and Alexander Tiskin. "Boundary properties of graphs for algorithmic graph problems." Theoretical Computer Science 412, no. 29 (July 2011): 3545–54. http://dx.doi.org/10.1016/j.tcs.2011.03.001.

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

Cicerone, Serafino, and Gabriele Di Stefano. "Getting new algorithmic results by extending distance-hereditary graphs via split composition." PeerJ Computer Science 7 (July 7, 2021): e627. http://dx.doi.org/10.7717/peerj-cs.627.

Full text
Abstract:
In this paper, we consider the graph class denoted as Gen(∗;P3,C3,C5). It contains all graphs that can be generated by the split composition operation using path P3, cycle C3, and any cycle C5 as components. This graph class extends the well-known class of distance-hereditary graphs, which corresponds, according to the adopted generative notation, to Gen(∗;P3,C3). We also use the concept of stretch number for providing a relationship between Gen(∗;P3,C3) and the hierarchy formed by the graph classes DH(k), with k ≥1, where DH(1) also coincides with the class of distance-hereditary graphs. For the addressed graph class, we prove there exist efficient algorithms for several basic combinatorial problems, like recognition, stretch number, stability number, clique number, domination number, chromatic number, and graph isomorphism. We also prove that graphs in the new class have bounded clique-width.
APA, Harvard, Vancouver, ISO, and other styles
10

Khalid Hamad Alnafisah, Khalid Hamad Alnafisah. "An Algorithmic Solution for the “Hair Ball” Problem in Data Visualization." Journal of engineering sciences and information technology 2, no. 4 (December 30, 2018): 86–66. http://dx.doi.org/10.26389/ajsrp.k220918.

Full text
Abstract:
The investigation and analysis of large and complex graphs is an important aspect of data visualization research, yet there is a need for entirely new, scalable approaches and methodologies for graph visualization. This can ultimately provide more insight into the structure and function of this complex graph (Hair Ball). To explain more, we need to find a methodology to develop a solution to present a “Tidy” graph with the minimal crossover between edges in the “Hair Balls.” In spite of the expanding significance of investigating and extensively analyzing and understanding very large graphs of data, the traditional way of visualizing graphs has difficulties scaling up, and typically ends up depicting these large graphs as “Hair Balls”. This traditional approach does indeed have a deeply intuitive foundation: nodes are depicted with a shape such as a circle, triangle or square, which are then connected by lines or curves that represent the edges. In any case, although there are many different ways to apply this basic underlying idea, it needs to be revisited in light of current and emerging needs for understanding increasingly complex crossover between edges in the graphs. The complex “Hair Ball,” which appears as an indecipherable graph, came from the crossover between edges. From our preliminary research, we found the major disadvantage in the Hair Balls graph was that it confused observers. Users may think there are some extra nodes; but in reality, there are not. Because there are many crossovers between edges in the Hair Balls, the impression also may affect observers’ understanding of the whole structure of the graph. Major problem-no effective reception of information from a “Hair Balls” graph-meaningless to observers.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Graph algorithmic"

1

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
2

Kanté, Mamadou Moustapha. "Graph structurings : some algorithmic applications." Thesis, Bordeaux 1, 2008. http://www.theses.fr/2008BOR13693/document.

Full text
Abstract:
Tous les problèmes définissables en logique du second ordre monadique peuvent être résolus en temps polynomial dans les classes de graphes qui ont une largeur de clique bornée. La largeur de clique est un paramètre de graphe défini de manière algébrique, c'est-à-dire, à partir d'opérations de composition de graphes. La largeur de rang, définie de manière combinatoire, est une notion équivalente à la largeur de clique des graphes non orientés. Nous donnons une caractérisation algébrique de la largeur de rang et nous montrons qu'elle est linéairement bornée par la largeur arborescente. Nous proposons également une notion de largeur de rang pour les graphes orientés et une relation de vertex-minor pour les graphes orientés. Nous montrons que les graphes orientés qui ont une largeur de rang bornée sont caractérisés par une liste finie de graphes orientés à exclure comme vertex-minor. Beaucoup de classes de graphes n'ont pas une largeur de rang bornée, par exemple, les graphes planaires. Nous nous intéressons aux systèmes d'étiquetage dans ces classes de graphes. Un système d'étiquetage pour une propriété P dans un graphe G, consiste à assigner une étiquette, aussi petite que possible, à chaque sommet de telle sorte que l'on puisse vérifier si G satisfait P en n'utilisant que les étiquettes des sommets. Nous montrons que si P est une propriété définissable en logique du premier ordre alors, certaines classes de graphes de largeur de clique localement bornée admettent un système d'étiquetage pour P avec des étiquettes de taille logarithmique. Parmi ces classes on peut citer les classes de graphes de degré borné, les graphes planaires et plus généralement les classes de graphes qui excluent un apex comme mineur et, les graphes d'intervalle unitaire. Si x et y sont deux sommets, X un ensemble de sommets et F un ensemble d'arêtes, nous notons Conn(x,y,X,F) la propriété qui vérifie dans un graphe donné si x et y sont connectés par un chemin, qui ne passe par aucun sommet de X si aucune arête de F. Cette propriété n'est pas définissable en logique du premier ordre. Nous montrons qu'elle admet un système d'étiquetage avec des étiquettes de taille logarithmique dans les graphes planaires. Nous montrons enfin que Conn(x,y,X,0) admet également un système d'étiquetage avec des étiquettes de taille logarithmique dans des classes de graphes qui sont définies comme des combinaisons de graphes qui ont une petite largeur de clique et telles que le graphe d'intersection de ces derniers est planaire et est de degré borné
Every property definable in onadic second order logic can be checked in polynomial-time on graph classes of bounded clique-width. Clique-width is a graph parameter defined in an algebraical way, i.e., with operations ``concatenating graphs'' and that generalize concatenation of words.Rank-width, defined in a combinatorial way, is equivalent to the clique-width of undirected graphs. We give an algebraic characterization of rank-width and we show that rank-width is linearly bounded in term of tree-width. We also propose a notion of ``rank-width'' of directed graphs and a vertex-minor inclusion for directed graphs. We show that directed graphs of bounded ``rank-width'' are characterized by a finite list of finite directed graphs to exclude as vertex-minor. Many graph classes do not have bounded rank-width, e.g., planar graphs. We are interested in labeling schemes on these graph classes. A labeling scheme for a property P in a graph G consists in assigning a label, as short as possible, to each vertex of G and such that we can verify if G satisfies P by just looking at the labels. We show that every property definable in first order logic admit labeling schemes with labels of logarithmic size on certain graph classes that have bounded local clique-width. Bounded degree graph classes, minor closed classes of graphs that exclude an apex graph as a minor have bounded local clique-width. If x and y are two vertices and X is a subset of the set of vertices and Y is a subset of the set of edges, we let Conn(x,y,X,Y) be the graph property x and y are connected by a path that avoids the vertices in X and the edges in Y. This property is not definable by a first order formula. We show that it admits a labeling scheme with labels of logarithmic size on planar graphs. We also show that Conn(x,y,X,0) admits short labeling schemes with labels of logarithmic size on graph classes that are ``planar gluings'' of graphs of small clique-width and with limited overlaps
APA, Harvard, Vancouver, ISO, and other styles
3

Rocha, Leonardo Sampaio. "Algorithmic aspects of graph colouring heuristics." Nice, 2012. https://tel.archives-ouvertes.fr/tel-00759408.

Full text
Abstract:
Une coloration propre d’un graphe est une fonction qui attribue une couleur à chaque sommet du graphe avec la restriction que deux sommets voisins ont des couleurs distinctes. Les colorations permettent de modéliser des problèmes d’ordonnancement, d’allocation de fréquences ou de registres. Le problème de trouver une coloration propre d’un graphe qui minimise le nombre de couleurs est un problème NP-difficile très connu. Dans cette thèse nous étudions le nombre de Grundy et le nombre b-chromatique des graphes, deux paramètres qui permettent d’évaluer quelques heuristiques pour le problème d’e la coloration propre. Nous commençons par dresser un état de l’art des résultats sur ces deux paramètres. Puis nous montrons que déterminer le nombre de Grundy est NP-difficile pour un graphe cordal et polynomial sur le graphe sans P5 bipartis. Ensuite nous montrons que déterminer le nombre b-chromatique est NP-difficile pour un graphe cordal et distance-héréditaire, et nous donnons des algorithmes polynomiaux pour certaines sous-classes de graphes blocs, complémentaires des graphes bipartis et P4-sparses. Nous considérons également la complexité à paramètre fixé de déterminer le nombre de Grundy (resp. Nombre b-chromatique) et en particulier, nous montrons que décider sir le nombre de Grundy (ou le nombre b-chromatique) d’un graphe G est au moins V(G)-k admet un algorithme FPT lorsque k est le paramètre. Enfin, nous considérons la complexité de nombreux problèmes liés à la comparaison du nombre de Grundy et nombre b-chromatique avec divers autres paramètres d’un graphe
A proper coloring of a graph is a function that assigns a color to each vertex with the restriction that adjacent vertices are assigned with distinct colors. Proper colorings are a natural model for many problems, like scheduling, frequency assignment and register allocation. The problem of finding a proper coloring of a graph with the minimum number of colors is a well-known NP-hard problem. In this thesis we study the Grundy number and the b-chromatic number of graphs, two parameters that evaluate some heuristics for finding proper colorings. We start by giving the state of the art of the results about these parameters. Then, we show that the problem of determining the Grundy Number of bipartite or chordal graphs is NP-hard, but it is solvable in polynomial time for P5-free bipartite graphs. After, we show that the problem of determining the b-chromatic number or a chordal distance-hereditary graph is NP-hard, and we give polynomial-time algorithms for some subclasses of block graphs, complement of bipartite graphs and p4-sparse graphs. We also consider the fixed-parameter tractability of determining the Grundy number and the b-chromatic number, and in particular we show that deciding if the Grundy number (or the b-chromatic number) of a graph G is at least V(G)-k admits an FPT algorithm when k is the parameter. Finally, we consider the computational complexity of many problems related to comparing the b-chromatic number and the Grundy number with various other related parameter of a graph
APA, Harvard, Vancouver, ISO, and other styles
4

De, Lara Nathan. "Algorithmic and software contributions to graph mining." Electronic Thesis or Diss., Institut polytechnique de Paris, 2020. http://www.theses.fr/2020IPPAT029.

Full text
Abstract:
Depuis l'invention du PageRank par Google pour les requêtes Web à la fin des années 1990, les algorithmes de graphe font partie de notre quotidien. Au milieu des années 2000, l'arrivée des réseaux sociaux a amplifié ce phénomène, élargissant toujours plus les cas d'usage de ces algorithmes. Les relations entre entités peuvent être de multiples sortes : relations symétriques utilisateur-utilisateur pour Facebook ou LinkedIn, relations asymétriques follower-followee pour Twitter, ou encore, relations bipartites utilisateur-contenu pour Netflix ou Amazon. Toutes soulèvent des problèmes spécifiques et les applications sont nombreuses : calcul de centralité pour la mesure d'influence, le partitionnement de nœuds pour la fouille de données, la classification de nœuds pour les recommandations ou l'embedding pour la prédiction de liens en sont quelques exemples.En parallèle, les conditions d'utilisation des algorithmes de graphe sont devenues plus contraignantes. D'une part, les jeux de données toujours plus gros avec des millions d'entités et parfois des milliards de relations limite la complexité asymptotique des algorithmes pour les applications industrielles. D'autre part, dans la mesure où ces algorithmes influencent nos vies, les exigences d'explicabilité et d'équité dans le domaine de l'intelligence artificielle augmentent. Les algorithmes de graphe ne font pas exception à la règle. L'Union européenne a par exemple publié un guide de conduite pour une IA fiable. Ceci implique de pousser encore plus loin l'analyse des modèles actuels, voire d'en proposer de nouveaux.Cette thèse propose des réponses ciblées via l'analyse d'algorithmes classiques, mais aussi de leurs extensions et variantes, voire d'algorithmes originaux. La capacité à passer à l'échelle restant un critère clé. Dans le sillage de ce que le projet Scikit-learn propose pour l'apprentissage automatique sur données vectorielles, nous estimons qu'il est important de rendre ces algorithmes accessibles au plus grand nombre et de démocratiser la manipulation de graphes. Nous avons donc développé un logiciel libre, Scikit-network, qui implémente et documente ces algorithmes de façon simple et efficace. Grâce à cet outil, nous pouvons explorer plusieurs tâches classiques telles que l'embedding de graphe, le partitionnement, ou encore la classification semi-supervisée
Since the introduction of Google's PageRank method for Web searches in the late 1990s, graph algorithms have been part of our daily lives. In the mid 2000s, the arrival of social networks has amplified this phenomenon, creating new use-cases for these algorithms. Relationships between entities can be of multiple types: user-user symmetric relationships for Facebook or LinkedIn, follower-followee asymmetric ones for Twitter or even user-content bipartite ones for Netflix or Amazon. They all come with their own challenges and the applications are numerous: centrality calculus for influence measurement, node clustering for knowledge discovery, node classification for recommendation or embedding for link prediction, to name a few.In the meantime, the context in which graph algorithms are applied has rapidly become more constrained. On the one hand, the increasing size of the datasets with millions of entities, and sometimes billions of relationships, bounds the asymptotic complexity of the algorithms for industrial applications. On the other hand, as these algorithms affect our daily lives, there is a growing demand for explanability and fairness in the domain of artificial intelligence in general. Graph mining is no exception. For example, the European Union has published a set of ethics guidelines for trustworthy AI. This calls for further analysis of the current models and even new ones.This thesis provides specific answers via a novel analysis of not only standard, but also extensions, variants, and original graph algorithms. Scalability is taken into account every step of the way. Following what the Scikit-learn project does for standard machine learning, we deem important to make these algorithms available to as many people as possible and participate in graph mining popularization. Therefore, we have developed an open-source software, Scikit-network, which implements and documents the algorithms in a simple and efficient way. With this tool, we cover several areas of graph mining such as graph embedding, clustering, and semi-supervised node classification
APA, Harvard, Vancouver, ISO, and other styles
5

Wolff, Tanya Layng. "Cayley networks, group, graph theoretic and algorithmic properties." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/mq22426.pdf.

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

Tamura, Takeyuki. "Graph Algorithmic Approaches for Structure Inferences in Bioinformatics." 京都大学 (Kyoto University), 2006. http://hdl.handle.net/2433/68893.

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

Jaeger, Mordechai. "An algorithmic approach to center location and related problems." Diss., The University of Arizona, 1992. http://hdl.handle.net/10150/185767.

Full text
Abstract:
Center location on cactus graphs. The p-center problem has been shown to be NP-hard for case of a general graph, yet polynomial algorithms exist for the case of a tree graph. Specifically, we consider "cactus graphs" where each edge is contained in at most one cycle. We show that the p-center problem on this class can be solved in polynomial time using a decomposition algorithm. We partition the graph into a set of subgraphs which are then solved sequentially. The solutions to the subgraphs are linked by a single parameter. The algorithm runs in polynomial time. Locating capacity limited centers on trees. The uncapacitated p-center problem on trees is solvable in polynomial time. We extend this result to include the case where each center can serve a limited number of customers and show that the capacitated p-center on trees can be solved in polynomial time when the capacities are identical. The algorithm consists of solving a capacitated covering problem and then using search routines to find the optimal domination radius. Center location on spheres. We discuss the unweighted center location problem. The following results are presented: (i) An O(n) time algorithm to solve the 1-center problem if the vertices are on one half of the sphere, and an O(n) time algorithm to check whether this condition holds. Both algorithms are based on presenting the problems as 3-dimensional convex programming problems with linear constraints and applying a pruning technique to find the optimum in O(n) time. (ii) An O(n$\sp3$ log n) time algorithm for the 2-center problem on the whole sphere. (iii) A reduction to show that the general p-center problem on a sphere is NP-hard. Locating hyperplanes on hypercubes. In linear regression models we are interested in locating a (d-1) dimensional hyperplane that will be as "close" as possible to existing vertices in the d-dimensional hypercube. The least squares criterion is usually applied for the linear fitting problem; while fitting according to the least absolute value ("minisum") seems to be "complicated". We solve fitting problems with the minisum criterion and present linear time algorithms when the dimension d is fixed. (Abstract shortened with permission of author.)
APA, Harvard, Vancouver, ISO, and other styles
8

Pandey, Arti. "Algorithmic aspects of domination and its variations." Thesis, IIT Delhi, 2016. http://localhost:8080/xmlui/handle/12345678/7038.

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

Thiebaut, Jocelyn. "Algorithmic and structural results on directed cycles in dense digraphs." Thesis, Montpellier, 2019. http://www.theses.fr/2019MONTS059.

Full text
Abstract:
Dans cette thèse, nous nous intéressons à quelques problèmes algorithmiques et structurels du packing de cycles (orientés) dans les graphes orientés denses. Ces problèmes sont notamment motivés par la compréhension de la structure de tels graphes, mais également car de nombreux problèmes algorithmiques sont faciles (résolubles en temps polynomial) sur des graphes orientés acycliques alors qu'il sont NP-difficiles sur les graphes orientés en général.Plus spécifiquement, nous étudions dans un premier temps le packing de cycles et le packing de triangles dans les tournois. Ces problèmes sont les duaux (d'un point de vue programmation linéaire) des problèmes de feedback arc/vertex set qui ont reçu beaucoup d'attention dans la littérature. Nous montrons entre autres qu'il n'y a pas d'algorithme polynomial pour trouver une collection maximale de cycles (respectivement triangles) sommet ou arc-disjointe dans les tournois, sauf si P = NP. Nous nous intéressons également aux algorithmes d'approximations et de complexité paramétrée de ces différents problèmes.Nous étudions ensuite plus en détail ces problèmes dans le cas spécifique où le tournoi admet un feedback arc set qui est un couplage, appelé sparse. Étonnamment, le problème reste difficile dans le cas des triangles sommet-disjoints, mais devient polynomial pour les triangles et cycles arc-disjoints. Ainsi, nous explorons l'approximation et la complexité paramétrée du cas sommet-disjoints dans les tournois sparses.Enfin, nous répondons positivement à une conjecture structurelle sur les bipartis complets k-réguliers par Manoussakis, Song et Zhang datant de 1994. En effet, nous démontrons que tous les digraphes de cette classe non isomorphes à un digraphe particulier possèdent pour tout p pair avec 4 leq p leq |V(D)| - 4 un cycle C de taille p tel que D V(C) est hamiltonien
In this thesis, we are interested in some algorithmic and structural problems of (oriented) cycle packing in dense digraphs. These problems are mainly motivated by understanding the structure of such graphs, but also because many algorithmic problems are easy (i.e. resolvable in polynomial time) on acyclic digraphs while they are NP-difficult in the general case.More specifically, we first study the packing of cycles and the packing of triangles in tournaments. These problems are the two dual problems (from a linear programming point of view) of feedback arc/vertex set that have received a lot of attention in literature. Among other things, we show that there is no polynomial algorithm to find a maximum collection of cycles (respectively triangles) vertex or arc-disjoint in tournaments, unless P = NP. We are also interested in algorithms of approximations and parameterized complexity of these different problems.Then, we study these problems in the specific case where the tournament admits a feedback arc set which is a matching. Such tournaments are said to be sparse. Surprisingly, the problem remains difficult in the case of vertex-disjoint triangles, but the packing of triangles and the packing of arc-disjoint cycles become polynomial. Thus, we explore the approximation and parameterized complexity of the vertex-disjoint case in sparse tournaments.Finally, we answer positively to a structural conjecture on k-regular bipartite tournaments by Manoussakis, Song and Zhang from 1994. Indeed, we show that all digraphs of this non-isomorphic class to a particular digraph have for every p even with 4 leq p leq |V(D)| - 4 a C cycle of size p such that D V(C) is Hamiltonian
APA, Harvard, Vancouver, ISO, and other styles
10

Kalzi, Hasan. "Graph Complexity Based on a Heuristic That Involves the Algorithmic Complexity Behaviour of Multiplex Networks on Graphs." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-302104.

Full text
Abstract:
Since determining the complexity of multiplex networks is an NP-hard problem, I decided to calculate the complexity of graphs using heuristics. I am the first in this path who did these kinds of calculations. I always wanted to define complexity as a mathematical characteristic in the structure of graphs. This investigation explores the behaviour of the algorithmic complexity of multiplex networks on graphs to discover if it is possible to extract a mathematical expression that can represent it. If we obtain a mathematical representation for graph complexity, we tackle this problem from the NP-hard problem area. It also can be used as one of the characteristics of the graph, e.g., the number of nodes, edges, or motifs of a specific size. Santoro and Nicosia, in their research, obtained the algorithmic complexity of multiplex networks is defined [1]. Thus, an approach that uses a heuristic strategy can be the easiest way to get near an optimal mathematical definition of the complexity of graphs. In this thesis, I re-introduce the recent representation of the algorithmic complexity [2] for multiplex networks from an algorithmic information theory [ 3 ] perspective. This definition depends mainly on Kolmogorov complexity [4, 5]. I studied the results of algorithmic complexity heuristic measurements on different and random networks that differ in size-4 motifs number. I found impressive results that show a logarithmic trend line (or maybe power trend line) for the algorithmic complexity with increasing the number of layers. Also, the algorithmic complexity decreases when the number of motifs increases. Thus, there can be a mathematical connection between the algorithmic complexity, the number of motifs, the number of layers, the number of edges and the number of nodes. Furthermore, more research is required to investigate and invent a mathematical expression between these characteristics. Also, more research is needed to assert the correctness of these conclusions on other kinds of networks with different motifs size.
Eftersom problemet med att bestämma komplexiteten hos flerfaldiga nätverk är ett NP-svårt problem, bestämde jag mig för att beräkna komplexiteten hos grafer med hjälp av heuristik. Jag är den första på den här vägen som gjorde den här typen av beräkningar. Jag ville alltid definiera komplexitet som en matematisk egenskap i diagramstrukturen. Denna uppsats undersöker beteendet hos den algoritmiska komplexiteten av flerfaldiga nätverk i grafer för att upptäcka om det är möjligt att extrahera ett matematiskt uttryck som kan representera det. Om vi får en matematisk representation för grafkomplexitet, hanterar vi detta problem från det NP- hårda problemområdet. Den kan också användas som en av diagrammets egenskaper, såsom antalet noder, kanter eller motiv av en viss storlek. Den algoritmiska komplexiteten av flerfaldiga nätverk definieras av Santoro och Nicosia i deras forskningspapper [1]. Således kan ett tillvägagångssätt som använder en heuristisk strategi vara det enklaste sättet att komma nära en optimal matematisk definition av komplexiteten i grafer. I denna avhandling introducerar jag den senaste representationen av den algoritmiska komplexiteten [2] för flerfaldiga nätverk ur ett algoritmiskt perspektiv för informationsteori [3]. Denna definition beror främst på Kolmogorov-komplexiteten [4, 5 ]. Jag studerade resultaten av de heuristiska algoritmiska komplexitetsmätningarna på olika och slumpmässiga nätverk som skiljer sig åt i storlek-4-motivnummer. Jag hittade imponerande resultat som visar en logaritmisk trendlinje (eller kanske krafttrendlinje) för den algoritmiska komplexiteten med att öka antalet lager. Den algoritmiska komplexiteten minskar också när antalet motiv ökar. Således kan det finnas en matematisk koppling mellan den algoritmiska komplexiteten, antalet motiv, antalet lager, antalet kanter och antalet noder. Dessutom krävs mer forskning för att undersöka och uppfinna ett matematiskt uttryck mellan dessa egenskaper. Dessutom behövs mer forskning för att hävda riktigheten av dessa slutsatser på andra olika typer av nätverk.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Graph algorithmic"

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

Algorithmic graph theory. London: Prentice-Hall, 1990.

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

Algorithmic graph theory. Cambridge [Cambridgeshire]: Cambridge University Press, 1985.

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

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

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

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

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

Nagamochi, Hiroshi. Algorithmic aspects of graph connectivity. New York: Cambridge University Press, 2008.

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

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

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

Chartrand, G. Applied and algorithmic graph theory. New York: McGraw-Hill, 1993.

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

Chartrand, G. Applied and algorithmic graph theory. London: McGraw-Hill, 1993.

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

Chartrand, Gary. Applied and algorithmic graph theory. New York: McGraw-Hill, 1993.

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

Book chapters on the topic "Graph algorithmic"

1

Hougardy, Stefan, and Jens Vygen. "Simple Graph Algorithms." In Algorithmic Mathematics, 85–90. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-39558-6_7.

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

Henning, Michael A., and Jan H. van Vuuren. "Algorithmic complexity." In Graph and Network Theory, 55–85. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-03857-0_3.

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

Chen, Jianer. "Algorithmic graph embeddings." In Lecture Notes in Computer Science, 151–60. Berlin, Heidelberg: Springer Berlin Heidelberg, 1995. http://dx.doi.org/10.1007/bfb0030829.

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

Gelfand, Natasha, and Roberto Tamassia. "Algorithmic Patterns for Orthogonal Graph Drawing." In Graph Drawing, 138–52. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/3-540-37623-2_11.

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

Castelló, R., R. Mili, and I. G. Tollis. "An Algorithmic Framework for Visualizing Statecharts." In Graph Drawing, 139–49. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/3-540-44541-2_13.

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

Zhang, Zhongyi, and Jiong Guo. "Colorful Graph Coloring." In Frontiers of Algorithmic Wisdom, 141–61. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-20796-9_11.

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

Taillard, Éric D. "Elements of Graphs and Complexity Theory." In Design of Heuristic Algorithms for Hard Optimization, 3–29. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-13714-3_1.

Full text
Abstract:
AbstractThis chapter recalls some elements and definitions in graph theory and complexity theory. On the one hand, basic algorithmic courses very often include graph algorithms. Some of these algorithms have simply been transposed to solve difficult optimization problems in a heuristic way. On the other hand, it is important to be able to determine whether a problem falls into the category of difficult problems. Indeed, one will not develop a heuristic algorithm if there is an efficient algorithm to find an exact solution. Another objective of this chapter is to make the book self-contained.
APA, Harvard, Vancouver, ISO, and other styles
8

Grohe, Martin. "Algorithmic Meta Theorems." In Graph-Theoretic Concepts in Computer Science, 30. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. http://dx.doi.org/10.1007/978-3-540-92248-3_3.

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

Kouroupas, Georgios, Evangelos Markakis, Christos Papadimitriou, Vasileios Rigas, and Martha Sideri. "The Web Graph as an Equilibrium." In Algorithmic Game Theory, 203–15. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015. http://dx.doi.org/10.1007/978-3-662-48433-3_16.

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

Lin, Tao, and Peter Eades. "Integration of declarative and algorithmic approaches for layout creation." In Graph Drawing, 376–87. Berlin, Heidelberg: Springer Berlin Heidelberg, 1995. http://dx.doi.org/10.1007/3-540-58950-3_392.

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

Conference papers on the topic "Graph algorithmic"

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

Bei, Xiaohui, Youming Qiao, and Shengyu Zhang. "Networked Fairness in Cake Cutting." In Twenty-Sixth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/508.

Full text
Abstract:
We introduce a graphical framework for fair division in cake cutting, where comparisons between agents are limited by an underlying network structure. We generalize the classical fairness notions of envy-freeness and proportionality in this graphical setting. An allocation is called envy-free on a graph if no agent envies any of her neighbor's share, and is called proportional on a graph if every agent values her own share no less than the average among her neighbors, with respect to her own measure. These generalizations enable new research directions in developing simple and efficient algorithms that can produce fair allocations under specific graph structures. On the algorithmic frontier, we first propose a moving-knife algorithm that outputs an envy-free allocation on trees. The algorithm is significantly simpler than the discrete and bounded envy-free algorithm introduced in [Aziz and Mackenzie, 2016] for compete graphs. Next, we give a discrete and bounded algorithm for computing a proportional allocation on transitive closure of trees, a class of graphs by taking a rooted tree and connecting all its ancestor-descendant pairs.
APA, Harvard, Vancouver, ISO, and other styles
3

Bonani, Andrea, Vincenzo Del Fatto, Gabriella Dodero, and Rosella Gennari. "Tangibles for Graph Algorithmic Thinking." In SIGCSE '18: The 49th ACM Technical Symposium on Computer Science Education. New York, NY, USA: ACM, 2018. http://dx.doi.org/10.1145/3159450.3162267.

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

Eiben, Eduard, Robert Ganian, Dušan Knop, and Sebastian Ordyniak. "Unary Integer Linear Programming with Structural Restrictions." 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/179.

Full text
Abstract:
Recently a number of algorithmic results have appeared which show the tractability of Integer Linear Programming (ILP) instances under strong restrictions on variable domains and/or coefficients (AAAI 2016, AAAI 2017, IJCAI 2017). In this paper, we target ILPs where neither the variable domains nor the coefficients are restricted by a fixed constant or parameter; instead, we only require that our instances can be encoded in unary. We provide new algorithms and lower bounds for such ILPs by exploiting the structure of their variable interactions, represented as a graph. Our first set of results focuses on solving ILP instances through the use of a graph parameter called clique-width, which can be seen as an extension of treewidth which also captures well-structured dense graphs. In particular, we obtain a polynomial-time algorithm for instances of bounded clique-width whose domain and coefficients are polynomially bounded by the input size, and we complement this positive result by a number of algorithmic lower bounds. Afterwards, we turn our attention to ILPs with acyclic variable interactions. In this setting, we obtain a complexity map for the problem with respect to the graph representation used and restrictions on the encoding.
APA, Harvard, Vancouver, ISO, and other styles
5

Rehman, Akif, Masab Ahmad, and Omer Khan. "Exploring accelerator and parallel graph algorithmic choices for temporal graphs." In PPoPP '20: 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York, NY, USA: ACM, 2020. http://dx.doi.org/10.1145/3380536.3380540.

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

Vajapeyam, Sridhar, and Michael Keefe. "Triangulated Surface Construction From Scattered 3-D Points." In ASME 1992 International Computers in Engineering Conference and Exposition. American Society of Mechanical Engineers, 1992. http://dx.doi.org/10.1115/cie1992-0087.

Full text
Abstract:
Abstract A three-dimensional analog to the Gabriel Graph structure is defined and an algorithmic procedure for the construction of a triangulated surface from scattered data points in three dimensions is developed based on the concept on three-dimensional Gabriel Graphs. The algorithm does not require the points to be in the form of a grid or on contours. The closest point 3-D Delaunay triangulation of the points is first constructed and the Delaunay triangles that satisfy the Gabriel Graph criterion are identified. From this set of triangles, extraneous triangles are removed, resulting in a triangulated open surface passing through all the given data points. This surface can then be subjected to smoothing algorithms if necessary and a smooth surface of the desired continuity can be constructed using available interpolation techniques. The algorithm can be used for constructing surfaces from scattered data in mechanical design, geographic terrain modeling and modeling biological surfaces from CT scans and MRI scans.
APA, Harvard, Vancouver, ISO, and other styles
7

Grande, Daniel, Felice Mancini, and Pradeep Radhakrishnan. "An Automated Graph Grammar Based Tool to Automatically Generate System Bond Graphs for Dynamic Analysis." In ASME 2016 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2016. http://dx.doi.org/10.1115/detc2016-59941.

Full text
Abstract:
This paper presents a graph grammar based automated tool that can generate bond graphs of various systems for dynamic analysis. A generic graph grammar based representation scheme has been developed for different system components and bond graph elements. Using that representation, grammar rules have been developed that enable interpreting a given system and generating bond graph through an algorithmic search process. Besides, the paper also demonstrates the utility of the proposed tool in classrooms to enhance value in bond graph based system dynamics education. The underlying technique, various examples and benefits of this automated tool will be highlighted.
APA, Harvard, Vancouver, ISO, and other styles
8

Harshvardhan, Adam Fidel, Nancy M. Amato, and Lawrence Rauchwerger. "An Algorithmic Approach to Communication Reduction in Parallel Graph Algorithms." In 2015 International Conference on Parallel Architecture and Compilation (PACT). IEEE, 2015. http://dx.doi.org/10.1109/pact.2015.34.

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

Schidler, André, and Stefan Szeider. "Computing Twin-width with SAT and Branch & Bound." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. California: International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/224.

Full text
Abstract:
The graph width-measure twin-width recently attracted great attention because of its solving power and generality. Many prominent NP-hard problems are tractable on graphs of bounded twin-width if a certificate for the twin-width bound is provided as an input. Bounded twin-width subsumes other prominent structural restrictions such as bounded treewidth and bounded rank-width. Computing such a certificate is NP-hard itself, already for twin-width 4, and the only known implemented algorithm for twin-width computation is based on a SAT encoding. In this paper, we propose two new algorithmic approaches for computing twin-width that significantly improve the state of the art. Firstly, we develop a SAT encoding that is far more compact than the known encoding and consequently scales to larger graphs. Secondly, we propose a new Branch & Bound algorithm for twin-width that, on many graphs, is significantly faster than the SAT encoding. It utilizes a sophisticated caching system for partial solutions. Both algorithmic approaches are based on new conceptual insights into twin-width computation, including the reordering of contractions.
APA, Harvard, Vancouver, ISO, and other styles
10

Borowiecki, Piotr. "Algorithmic bounds on the chromatic number of a graph." In 2008 1st International Conference on Information Technology (IT 2008). IEEE, 2008. http://dx.doi.org/10.1109/inftech.2008.4621642.

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

Reports on the topic "Graph algorithmic"

1

Grossman, Max, Howard Porter Pritchard Jr., Zoran Budimlic, and Vivek Sarkar. Graph 500 on OpenSHMEM: Using a Practical Survey of Past Work to Motivate Novel Algorithmic Developments. Office of Scientific and Technical Information (OSTI), December 2016. http://dx.doi.org/10.2172/1338682.

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

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
4

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
5

Striuk, Andrii, Olena Rybalchenko, and Svitlana Bilashenko. Development and Using of a Virtual Laboratory to Study the Graph Algorithms for Bachelors of Software Engineering. [б. в.], November 2020. http://dx.doi.org/10.31812/123456789/4462.

Full text
Abstract:
The paper presents an analysis of the importance of studying graph algorithms, the reasons for the need to implement this project and its subsequent use. The existing analogues analysis is carried out, due to which a list of advantages and disadvantages is formed and taken into account in developing the virtual laboratory. A web application is created that clearly illustrates the work of graph algorithms, such as Depth-First Search, Dijkstra’s Shortest Path, Floyd- Warshall, Kruskal Minimum Cost Spanning Tree Algorithm. A simple and user- friendly interface is developed and it is supported by all popular browsers. The software product is provided with user registration and authorization functions, chat communication, personal cabinet editing and viewing the statistics on web- application use. An additional condition is taken into account at the design stage, namely the flexibility of the architecture, which envisaged the possibility of easy expansion of an existing functionality. Virtual laboratory is used at Kryvyi Rih National University to training students of specialty 121 Software Engineering in the disciplines “Algorithms and Data Structures” and “Discrete Structures”.
APA, Harvard, Vancouver, ISO, and other styles
6

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
7

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
8

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
9

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
10

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