Journal articles: 'Graph theory techniques'

1

Arsic, Branko, Dragos Cvetkovic, Slobodan Simic, and Milan Skaric. "Graph spectral techniques in computer sciences." Applicable Analysis and Discrete Mathematics 6, no. 1 (2012): 1–30. http://dx.doi.org/10.2298/aadm111223025a.

Full text

Abstract:

We give a survey of graph spectral techniques used in computer sciences. The survey consists of a description of particular topics from the theory of graph spectra independently of the areas of Computer science in which they are used. We have described the applications of some important graph eigenvalues (spectral radius, algebraic connectivity, the least eigenvalue etc.), eigenvectors (principal eigenvector, Fiedler eigenvector and other), spectral reconstruction problems, spectra of random graphs, Hoffman polynomial, integral graphs etc. However, for each described spectral technique we indicate the fields in which it is used (e.g. in modelling and searching Internet, in computer vision, pattern recognition, data mining, multiprocessor systems, statistical databases, and in several other areas). We present some novel mathematical results (related to clustering and the Hoffman polynomial) as well.

APA, Harvard, Vancouver, ISO, and other styles

2

Dobrinen, Natasha. "The Ramsey theory of the universal homogeneous triangle-free graph." Journal of Mathematical Logic 20, no. 02 (January 28, 2020): 2050012. http://dx.doi.org/10.1142/s0219061320500129.

Full text

Abstract:

The universal homogeneous triangle-free graph, constructed by Henson [A family of countable homogeneous graphs, Pacific J. Math. 38(1) (1971) 69–83] and denoted [Formula: see text], is the triangle-free analogue of the Rado graph. While the Ramsey theory of the Rado graph has been completely established, beginning with Erdős–Hajnal–Posá [Strong embeddings of graphs into coloured graphs, in Infinite and Finite Sets. Vol.[Formula: see text] , eds. A. Hajnal, R. Rado and V. Sós, Colloquia Mathematica Societatis János Bolyai, Vol. 10 (North-Holland, 1973), pp. 585–595] and culminating in work of Sauer [Coloring subgraphs of the Rado graph, Combinatorica 26(2) (2006) 231–253] and Laflamme–Sauer–Vuksanovic [Canonical partitions of universal structures, Combinatorica 26(2) (2006) 183–205], the Ramsey theory of [Formula: see text] had only progressed to bounds for vertex colorings [P. Komjáth and V. Rödl, Coloring of universal graphs, Graphs Combin. 2(1) (1986) 55–60] and edge colorings [N. Sauer, Edge partitions of the countable triangle free homogenous graph, Discrete Math. 185(1–3) (1998) 137–181]. This was due to a lack of broadscale techniques. We solve this problem in general: For each finite triangle-free graph [Formula: see text], there is a finite number [Formula: see text] such that for any coloring of all copies of [Formula: see text] in [Formula: see text] into finitely many colors, there is a subgraph of [Formula: see text] which is again universal homogeneous triangle-free in which the coloring takes no more than [Formula: see text] colors. This is the first such result for a homogeneous structure omitting copies of some nontrivial finite structure. The proof entails developments of new broadscale techniques, including a flexible method for constructing trees which code [Formula: see text] and the development of their Ramsey theory.

APA, Harvard, Vancouver, ISO, and other styles

3

Young, Derek. "Techniques for determining equality of the maximum nullity and the zero forcing number of a graph." Electronic Journal of Linear Algebra 37 (May 10, 2021): 295–315. http://dx.doi.org/10.13001/ela.2021.4967.

Full text

Abstract:

It is known that the zero forcing number of a graph is an upper bound for the maximum nullity of the graph (see [AIM Minimum Rank - Special Graphs Work Group (F. Barioli, W. Barrett, S. Butler, S. Cioab$\breve{\text{a}}$, D. Cvetkovi$\acute{\text{c}}$, S. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha, W. So, D. Stevanovi$\acute{\text{c}}$, H. van der Holst, K. Vander Meulen, and A. Wangsness). Linear Algebra Appl., 428(7):1628--1648, 2008]). In this paper, we search for characteristics of a graph that guarantee the maximum nullity of the graph and the zero forcing number of the graph are the same by studying a variety of graph parameters that give lower bounds on the maximum nullity of a graph. Inparticular, we introduce a new graph parameter which acts as a lower bound for the maximum nullity of the graph. As a result, we show that the Aztec Diamond graph's maximum nullity and zero forcing number are the same. Other graph parameters that are considered are a Colin de Verdiére type parameter and vertex connectivity. We also use matrices, such as a divisor matrix of a graph and an equitable partition of the adjacency matrix of a graph, to establish a lower bound for the nullity of the graph's adjacency matrix.

APA, Harvard, Vancouver, ISO, and other styles

4

Olifer, Dmitrij, Nikolaj Goranin, Antanas Cenys, Arnas Kaceniauskas, and Justinas Janulevicius. "Defining the Minimum Security Baseline in a Multiple Security Standards Environment by Graph Theory Techniques." Applied Sciences 9, no. 4 (February 17, 2019): 681. http://dx.doi.org/10.3390/app9040681.

Full text

Abstract:

One of the best ways to protect an organization’s assets is to implement security requirements defined by different standards or best practices. However, such an approach is complicated and requires specific skills and knowledge. In case an organization applies multiple security standards, several problems can arise related to overlapping or conflicting security requirements, increased expenses on security requirement implementation, and convenience of security requirement monitoring. To solve these issues, we propose using graph theory techniques. Graphs allow the presentation of security requirements of a standard as graph vertexes and edges between vertexes, and would show the relations between different requirements. A vertex cover algorithm is proposed for minimum security requirement identification, while graph isomorphism is proposed for comparing existing organization controls against a set of minimum requirements identified in the previous step.

APA, Harvard, Vancouver, ISO, and other styles

5

Barik, Mridul Sankar, Anirban Sengupta, and Chandan Mazumdar. "Attack Graph Generation and Analysis Techniques." Defence Science Journal 66, no. 6 (October 31, 2016): 559. http://dx.doi.org/10.14429/dsj.66.10795.

Full text

Abstract:

As computer networks are emerging in everyday life, network security has become an important issue. Simultaneously, attacks are becoming more sophisticated, making the defense of computer networks increasingly difficult. Attack graph is a modeling tool used in the assessment of security of enterprise networks. Since its introduction a considerable amount of research effort has been spent in the development of theory and practices around the idea of attack graph. This paper presents a consolidated view of major attack graph generation and analysis techniques.

APA, Harvard, Vancouver, ISO, and other styles

6

Cowan, David, and Norman R. Reilly. "Characterizations of Schützenberger graphs in terms of their automorphism groups and fundamental groups." Glasgow Mathematical Journal 35, no. 3 (September 1993): 275–91. http://dx.doi.org/10.1017/s0017089500009861.

Full text

Abstract:

AbstractThe importance of the fundamental group of a graph in group theory has been well known for many years. The recent work of Meakin, Margolis and Stephen has shown how effective graph theoretic techniques can be in the study of word problems in inverse semigroups. Our goal here is to characterize those deterministic inverse word graphs that are Schutzenberger graphs and consider how deterministic inverse word graphs and Schutzenberger graphs can be constructed from subgroups of free groups.

APA, Harvard, Vancouver, ISO, and other styles

7

Breen, Jane, Steve Butler, Nicklas Day, Colt DeArmond, Kate Lorenzen, Haoyang Qian, and Jacob Riesen. "Computing Kemeny's constant for a barbell graph." Electronic Journal of Linear Algebra 35 (December 9, 2019): 583–98. http://dx.doi.org/10.13001/ela.2019.5175.

Full text

Abstract:

In a graph theory setting, Kemeny’s constant is a graph parameter which measures a weighted average of the mean first passage times in a random walk on the vertices of the graph. In one sense, Kemeny’s constant is a measure of how well the graph is ‘connected’. An explicit computation for this parameter is given for graphs of order n consisting of two large cliques joined by an arbitrary number of parallel paths of equal length, as well as for two cliques joined by two paths of different length. In each case, Kemeny’s constant is shown to be O(n3), which is the largest possible order of Kemeny’s constant for a graph on n vertices. The approach used is based on interesting techniques in spectral graph theory and includes a generalization of using twin subgraphs to find the spectrum of a graph.

APA, Harvard, Vancouver, ISO, and other styles

8

Sason, Igal. "A Generalized Information-Theoretic Approach for Bounding the Number of Independent Sets in Bipartite Graphs." Entropy 23, no. 3 (February 25, 2021): 270. http://dx.doi.org/10.3390/e23030270.

Full text

Abstract:

This paper studies the problem of upper bounding the number of independent sets in a graph, expressed in terms of its degree distribution. For bipartite regular graphs, Kahn (2001) established a tight upper bound using an information-theoretic approach, and he also conjectured an upper bound for general graphs. His conjectured bound was recently proved by Sah et al. (2019), using different techniques not involving information theory. The main contribution of this work is the extension of Kahn’s information-theoretic proof technique to handle irregular bipartite graphs. In particular, when the bipartite graph is regular on one side, but may be irregular on the other, the extended entropy-based proof technique yields the same bound as was conjectured by Kahn (2001) and proved by Sah et al. (2019).

APA, Harvard, Vancouver, ISO, and other styles

9

Devriendt, Karel, and Piet Van Mieghem. "The simplex geometry of graphs." Journal of Complex Networks 7, no. 4 (January 29, 2019): 469–90. http://dx.doi.org/10.1093/comnet/cny036.

Full text

Abstract:

AbstractGraphs are a central object of study in various scientific fields, such as discrete mathematics, theoretical computer science and network science. These graphs are typically studied using combinatorial, algebraic or probabilistic methods, each of which highlights the properties of graphs in a unique way. Here, we discuss a novel approach to study graphs: the simplex geometry (a simplex is a generalized triangle). This perspective, proposed by Miroslav Fiedler, introduces techniques from (simplex) geometry into the field of graph theory and conversely, via an exact correspondence. We introduce this graph-simplex correspondence, identify a number of basic connections between graph characteristics and simplex properties, and suggest some applications as example.

APA, Harvard, Vancouver, ISO, and other styles

10

Et. al., M. Sailaja,. "Ensemble Distributed Search-FSGM-CRD Compressed Cache Algorithm for Large Datasets." Turkish Journal of Computer and Mathematics Education (TURCOMAT) 12, no. 2 (April 11, 2021): 2854–58. http://dx.doi.org/10.17762/turcomat.v12i2.2317.

Full text

Abstract:

Frequent sub-graph mining (FSM) is a alternative of frequent pattern mining where patterns are graphs. Among the entities, graph based representation is utilized to effectively represent the complex relationships. Various graph mining techniques are developed from the past many years, most the challenging tasks in graph mining is frequent sub-graph mining (FSM). In FSM many of the existing algorithms consider only graph based structure, the relationships based on entities involved and strength is not considered. It is very important to handle the complex and huge data. There is very huge demand in distributed computational approaches. In this paper, An Ensemble Distributed Search-FSGM-CRD Compressed Cache Algorithm is developed and implemented to find frequent sub graphs

APA, Harvard, Vancouver, ISO, and other styles

11

Cvetkovic, Dragos, Tatjana Davidovic, and Irena Jovanovic. "Some new models for multiprocessor interconnection networks." Yugoslav Journal of Operations Research 26, no. 4 (2016): 423–39. http://dx.doi.org/10.2298/yjor160315020c.

Full text

Abstract:

A multiprocessor system can be modeled by a graph G. The vertices of G correspond to processors while edges represent links between processors. To find suitable models for multiprocessor interconnection networks (briefly MINs), one can apply tools and techniques of spectral graph theory. In this paper, we extend some of the existing results and present several graphs which could serve as models for efficient MINs based on the small values of the previously introduced graph tightness. These examples of possible MINs arise as a result of some well-known and widely used graph operations. We also examine the suitability of strongly regular graphs (briefly SRGs) to model MINs, and prove the uniqueness of some of them.

APA, Harvard, Vancouver, ISO, and other styles

12

Ouahada, Khmaies, and Hendrik C. Ferreira. "New Distance Concept and Graph Theory Approach for Certain Coding Techniques Design and Analysis." Communications in Applied and Industrial Mathematics 10, no. 1 (January 1, 2019): 53–70. http://dx.doi.org/10.1515/caim-2019-0012.

Full text

Abstract:

Abstract A New graph distance concept introduced for certain coding techniques helped in their design and analysis as in the case of distance-preserving mappings and spectral shaping codes. A graph theoretic construction, mapping binary sequences to permutation sequences and inspired from the k-cube graph has reached the upper bound on the sum of the distances for certain values of the length of the permutation sequence. The new introduced distance concept in the k-cube graph helped better understanding and analyzing for the first time the concept of distance-reducing mappings. A combination of distance and the index-permutation graph concepts helped uncover and verify certain properties of spectral null codes, which were previously difficult to analyze.

APA, Harvard, Vancouver, ISO, and other styles

13

Clack, Chris, Stuart Clayman, and David Parrott. "Lexical profiling: theory and practice." Journal of Functional Programming 5, no. 2 (April 1995): 225–77. http://dx.doi.org/10.1017/s0956796800001337.

Full text

Abstract:

AbstractThis paper addresses the issue of analysing the run-time behaviour of lazy, higher-order functional programs. We examine the difference between the way that functional programmers and functional language implementors view program behaviour. Existing profiling techniques are discussed and a new technique is proposed which produces results that are straightforward for programmers to assimilate. The new technique, which we call lexical profiling, collects information about the run-time behaviour of functional programs, and reports the results with respect to the original source code rather than simply listing the actions performed at run-time. Lexical profiling complements implementation-specific profiling and is important because it provides a view of program activity which is largely independent of the underlying evaluation mechanism. Using the lexical profiler, programmers may easily relate results back to the source program. We give a full implementation of the lexical profiling technique for a sequential, interpretive graph reduction engine, and extensions for compiled and parallel graph reduction are discussed.

APA, Harvard, Vancouver, ISO, and other styles

14

Cvetkovic, Dragos. "Spectral recognition of graphs." Yugoslav Journal of Operations Research 22, no. 2 (2012): 145–61. http://dx.doi.org/10.2298/yjor120925025c.

Full text

Abstract:

At some time, in the childhood of spectral graph theory, it was conjectured that non-isomorphic graphs have different spectra, i.e. that graphs are characterized by their spectra. Very quickly this conjecture was refuted and numerous examples and families of non-isomorphic graphs with the same spectrum (cospectral graphs) were found. Still some graphs are characterized by their spectra and several mathematical papers are devoted to this topic. In applications to computer sciences, spectral graph theory is considered as very strong. The benefit of using graph spectra in treating graphs is that eigenvalues and eigenvectors of several graph matrices can be quickly computed. Spectral graph parameters contain a lot of information on the graph structure (both global and local) including some information on graph parameters that, in general, are computed by exponential algorithms. Moreover, in some applications in data mining, graph spectra are used to encode graphs themselves. The Euclidean distance between the eigenvalue sequences of two graphs on the same number of vertices is called the spectral distance of graphs. Some other spectral distances (also based on various graph matrices) have been considered as well. Two graphs are considered as similar if their spectral distance is small. If two graphs are at zero distance, they are cospectral. In this sense, cospectral graphs are similar. Other spectrally based measures of similarity between networks (not necessarily having the same number of vertices) have been used in Internet topology analysis, and in other areas. The notion of spectral distance enables the design of various meta-heuristic (e.g., tabu search, variable neighbourhood search) algorithms for constructing graphs with a given spectrum (spectral graph reconstruction). Several spectrally based pattern recognition problems appear in many areas (e.g., image segmentation in computer vision, alignment of protein-protein interaction networks in bio-informatics, recognizing hard instances for combinatorial optimization problems such as the travelling salesman problem). We give a survey of such and other graph spectral recognition techniques used in computer sciences.

APA, Harvard, Vancouver, ISO, and other styles

15

Nedunuri, Srinivas, William R. Cook, and Douglas R. Smith. "Theory and Techniques for Synthesizing a Family of Graph Algorithms." Electronic Proceedings in Theoretical Computer Science 84 (July 3, 2012): 33–46. http://dx.doi.org/10.4204/eptcs.84.3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

LEWIS, CATHRYN M. "The use of graph theory techniques to investigate genealogical structure." Mathematical Medicine and Biology 9, no. 3 (1992): 145–59. http://dx.doi.org/10.1093/imammb/9.3.145.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Ibrahim, Rania, and David F. Gleich. "Local hypergraph clustering using capacity releasing diffusion." PLOS ONE 15, no. 12 (December 23, 2020): e0243485. http://dx.doi.org/10.1371/journal.pone.0243485.

Full text

Abstract:

Local graph clustering is an important machine learning task that aims to find a well-connected cluster near a set of seed nodes. Recent results have revealed that incorporating higher order information significantly enhances the results of graph clustering techniques. The majority of existing research in this area focuses on spectral graph theory-based techniques. However, an alternative perspective on local graph clustering arises from using max-flow and min-cut on the objectives, which offer distinctly different guarantees. For instance, a new method called capacity releasing diffusion (CRD) was recently proposed and shown to preserve local structure around the seeds better than spectral methods. The method was also the first local clustering technique that is not subject to the quadratic Cheeger inequality by assuming a good cluster near the seed nodes. In this paper, we propose a local hypergraph clustering technique called hypergraph CRD (HG-CRD) by extending the CRD process to cluster based on higher order patterns, encoded as hyperedges of a hypergraph. Moreover, we theoretically show that HG-CRD gives results about a quantity called motif conductance, rather than a biased version used in previous experiments. Experimental results on synthetic datasets and real world graphs show that HG-CRD enhances the clustering quality.

APA, Harvard, Vancouver, ISO, and other styles

18

Sebastian, Arya, John N. Mordeson, and Sunil Mathew. "Generalized Fuzzy Graph Connectivity Parameters with Application to Human Trafficking." Mathematics 8, no. 3 (March 16, 2020): 424. http://dx.doi.org/10.3390/math8030424.

Full text

Abstract:

Graph models are fundamental in network theory. But normalization of weights are necessary to deal with large size networks like internet. Most of the research works available in the literature have been restricted to an algorithmic perspective alone. Not much have been studied theoretically on connectivity of normalized networks. Fuzzy graph theory answers to most of the problems in this area. Although the concept of connectivity in fuzzy graphs has been widely studied, one cannot find proper generalizations of connectivity parameters of unweighted graphs. Generalizations for some of the existing vertex and edge connectivity parameters in graphs are attempted in this article. New parameters are compared with the old ones and generalized values are calculated for some of the major classes like cycles and trees in fuzzy graphs. The existence of super fuzzy graphs with higher connectivity values are established for both old and new parameters. The new edge connectivity values for some wider classes of fuzzy graphs are also obtained. The generalizations bring substantial improvements in fuzzy graph clustering techniques and allow a smooth theoretical alignment. Apart from these, a new class of fuzzy graphs called generalized t-connected fuzzy graphs are studied. An algorithm for clustering the vertices of a fuzzy graph and an application related to human trafficking are also proposed.

APA, Harvard, Vancouver, ISO, and other styles

19

Farrugia, Alexander, and Irene Sciriha. "On the Main Eigenvalues of Universal Adjacency Matrices and U-Controllable Graphs." Electronic Journal of Linear Algebra 30 (February 8, 2015): 812–26. http://dx.doi.org/10.13001/1081-3810.2935.

Full text

Abstract:

A universal adjacency matrix U of a graph G is a linear combination of the 0â1 adjacency matrix A, the diagonal matrix of vertex degrees D, the identity matrix I and the matrix J each of whose entries is 1. A main eigenvalue of U is an eigenvalue having an eigenvector that is not orthogonal to the allâones vector. It is shown that the number of distinct main eigenvalues of U associated with a simple graph G is at most the number of orbits of any automorphism of G. The definition of a Uâcontrollable graph is given using controlâtheoretic techniques and several necessary and sufficient conditions for a graph to be Uâcontrollable are determined. It is then demonstrated that Uâcontrollable graphs are asymmetric and that the converse is false, showing that there exist both regular and nonâregular asymmetric graphs that are not Uâcontrollable for any universal adjacency matrix U. To aid in the discovery of these counterexamples, a gammaâLaplacian matrix L(gamma) is used, which is a simplified form of U. It is proved that any U-controllable graph is a L(gamma)âcontrollable graph for some parameter gamma.

APA, Harvard, Vancouver, ISO, and other styles

20

Reibenspies, J. H. "Enumeration and Classification of Anomaly/Peak Bases in Two-Dimensional Intensity Histograms. Application of Graph Theory to Crystallographic Data Imaging." Journal of Applied Crystallography 29, no. 3 (June 1, 1996): 241–45. http://dx.doi.org/10.1107/s0021889895015354.

Full text

Abstract:

Bragg-event peaks, spikes, intensity streaks and other anomalies generate abnormal regions in two-dimensional intensity histograms from area-detector images. Examination of the shapes of these regions can contribute to the identification of the types of phenomena that generated them. The points that define the anomaly bases, when connected with imaginary lines, form unique graphs. Individual graphs, in turn, can be enumerated by employing graph-theoretical notation and the graph shapes classified. The number of lines in any given graph can also be determined by summing the degrees of the graph points and dividing by two. The ratio of the number of lines per point is a direct indication of the shape of the anomaly base. Long linear and curved shapes, like those associated with intensity streaks and powder rings, will have small lines-per-point ratios, while compact round, square or oval shapes, similar to those belonging to Bragg-event peaks, will have larger lines-per-point ratios. For any given number of points (Np ), for any given graph, the minimum number of lines (q) will equal Np − 1, while the maximum number of lines (q max, Np ) is determined from a round-shaped graph. A graph-shape parameter (GS) can thus be defined as (q − Np − 1)/(q max. Np − Np − 1), where a value near one indicates a round graph shape and a value near zero indicates a linear graph shape. The application of graph-theoretical techniques to anomaly bases can thus provide insight into the nature of the intensities distributed throughout the two-dimensional crystallographic data image.

APA, Harvard, Vancouver, ISO, and other styles

21

ECHAHED, RACHID. "Foreword: special issue on term and graph rewriting." Mathematical Structures in Computer Science 28, no. 8 (July 6, 2018): 1287–89. http://dx.doi.org/10.1017/s0960129518000191.

Full text

Abstract:

Rewriting techniques constitute a foundational theory of computing science. They are being investigated for several structures, such as lambda-terms, strings, first-order terms or graphs, and have been successfully used in many areas such as programming languages, automated reasoning, program verification, security, etc. The growing interest in this research area is witnessed by the leading international events, such as ICGT (International Conference on Graph Transformation) and the recent FSCD conference (International Conference on Formal Structures for Computation and Deduction), which gathers all topics of the former international conferences RTA (Rewriting Techniques and Applications) and TLCA (Typed Lambda Calculi and Applications). During the last decade, a particular interest has been devoted to the study of the impact of shared structures in term and graph rewriting through the international workshops editions of TERMGRAPH and GCM (Graph Computation Models).

APA, Harvard, Vancouver, ISO, and other styles

22

Jiqiang Zhai, and Keqi Wang. "Optimization of Probabilistic Packet Marking Traceback Techniques based on Graph Theory." INTERNATIONAL JOURNAL ON Advances in Information Sciences and Service Sciences 5, no. 7 (April 15, 2013): 511–21. http://dx.doi.org/10.4156/aiss.vol5.issue7.60.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Dhulipala, Laxman, Guy E. Blelloch, and Julian Shun. "Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable." ACM Transactions on Parallel Computing 8, no. 1 (April 2021): 1–70. http://dx.doi.org/10.1145/3434393.

Full text

Abstract:

There has been significant recent interest in parallel graph processing due to the need to quickly analyze the large graphs available today. Many graph codes have been designed for distributed memory or external memory. However, today even the largest publicly-available real-world graph (the Hyperlink Web graph with over 3.5 billion vertices and 128 billion edges) can fit in the memory of a single commodity multicore server. Nevertheless, most experimental work in the literature report results on much smaller graphs, and the ones for the Hyperlink graph use distributed or external memory. Therefore, it is natural to ask whether we can efficiently solve a broad class of graph problems on this graph in memory. This paper shows that theoretically-efficient parallel graph algorithms can scale to the largest publicly-available graphs using a single machine with a terabyte of RAM, processing them in minutes. We give implementations of theoretically-efficient parallel algorithms for 20 important graph problems. We also present the interfaces, optimizations, and graph processing techniques that we used in our implementations, which were crucial in enabling us to process these large graphs quickly. We show that the running times of our implementations outperform existing state-of-the-art implementations on the largest real-world graphs. For many of the problems that we consider, this is the first time they have been solved on graphs at this scale. We have made the implementations developed in this work publicly-available as the Graph Based Benchmark Suite (GBBS).

APA, Harvard, Vancouver, ISO, and other styles

24

Nair, Aditya G., and Kunihiko Taira. "Network-theoretic approach to sparsified discrete vortex dynamics." Journal of Fluid Mechanics 768 (March 10, 2015): 549–71. http://dx.doi.org/10.1017/jfm.2015.97.

Full text

Abstract:

We examine discrete vortex dynamics in two-dimensional flow through a network-theoretic approach. The interaction of the vortices is represented with a graph, which allows the use of network-theoretic approaches to identify key vortex-to-vortex interactions. We employ sparsification techniques on these graph representations based on spectral theory to construct sparsified models and evaluate the dynamics of vortices in the sparsified set-up. Identification of vortex structures based on graph sparsification and sparse vortex dynamics is illustrated through an example of point-vortex clusters interacting amongst themselves. We also evaluate the performance of sparsification with increasing number of point vortices. The sparsified-dynamics model developed with spectral graph theory requires a reduced number of vortex-to-vortex interactions but agrees well with the full nonlinear dynamics. Furthermore, the sparsified model derived from the sparse graphs conserves the invariants of discrete vortex dynamics. We highlight the similarities and differences between the present sparsified-dynamics model and reduced-order models.

APA, Harvard, Vancouver, ISO, and other styles

25

Razvenskaya, Olga O. "On new algorithmic techniques for the weighted vertex coloring problem." Zhurnal Srednevolzhskogo Matematicheskogo Obshchestva 22, no. 4 (December 31, 2020): 442–48. http://dx.doi.org/10.15507/2079-6900.22.202004.442-448.

Full text

Abstract:

The classical NP-hard weighted vertex coloring problem consists in minimizing the number of colors in colorings of vertices of a given graph so that, for each vertex, the number of its colors equals a given weight of the vertex and adjacent vertices receive distinct colors. The weighted chromatic number is the smallest number of colors in these colorings. There are several polynomial-time algorithmic techniques for designing efficient algorithms for the weighted vertex coloring problem. For example, standard techniques of this kind are the modular graph decomposition and the graph decomposition by separating cliques. This article proposes new polynomial-time methods for graph reduction in the form of removing redundant vertices and recomputing weights of the remaining vertices so that the weighted chromatic number changes in a controlled manner. We also present a method of reducing the weighted vertex coloring problem to its unweighted version and its application. This paper contributes to the algorithmic graph theory.

APA, Harvard, Vancouver, ISO, and other styles

26

Galanis, Andreas, Leslie Ann Goldberg, and James Stewart. "Fast Algorithms for General Spin Systems on Bipartite Expanders." ACM Transactions on Computation Theory 13, no. 4 (December 31, 2021): 1–18. http://dx.doi.org/10.1145/3470865.

Full text

Abstract:

A spin system is a framework in which the vertices of a graph are assigned spins from a finite set. The interactions between neighbouring spins give rise to weights, so a spin assignment can also be viewed as a weighted graph homomorphism. The problem of approximating the partition function (the aggregate weight of spin assignments) or of sampling from the resulting probability distribution is typically intractable for general graphs. In this work, we consider arbitrary spin systems on bipartite expander Δ-regular graphs, including the canonical class of bipartite random Δ-regular graphs. We develop fast approximate sampling and counting algorithms for general spin systems whenever the degree and the spectral gap of the graph are sufficiently large. Roughly, this guarantees that the spin system is in the so-called low-temperature regime. Our approach generalises the techniques of Jenssen et al. and Chen et al. by showing that typical configurations on bipartite expanders correspond to “bicliques” of the spin system; then, using suitable polymer models, we show how to sample such configurations and approximate the partition function in Õ( n 2 ) time, where n is the size of the graph.

APA, Harvard, Vancouver, ISO, and other styles

27

Wu, Jieting, Feiyu Zhu, Xin Liu, and Hongfeng Yu. "An Information-Theoretic Framework for Evaluating Edge Bundling Visualization." Entropy 20, no. 9 (August 21, 2018): 625. http://dx.doi.org/10.3390/e20090625.

Full text

Abstract:

Edge bundling is a promising graph visualization approach to simplifying the visual result of a graph drawing. Plenty of edge bundling methods have been developed to generate diverse graph layouts. However, it is difficult to defend an edge bundling method with its resulting layout against other edge bundling methods as a clear theoretic evaluation framework is absent in the literature. In this paper, we propose an information-theoretic framework to evaluate the visual results of edge bundling techniques. We first illustrate the advantage of edge bundling visualizations for large graphs, and pinpoint the ambiguity resulting from drawing results. Second, we define and quantify the amount of information delivered by edge bundling visualization from the underlying network using information theory. Third, we propose a new algorithm to evaluate the resulting layouts of edge bundling using the amount of the mutual information between a raw network dataset and its edge bundling visualization. Comparison examples based on the proposed framework between different edge bundling techniques are presented.

APA, Harvard, Vancouver, ISO, and other styles

28

Sakr, Sherif, and Ghazi Al-Naymat. "Efficient Relational Techniques for Processing Graph Queries." Journal of Computer Science and Technology 25, no. 6 (November 2010): 1237–55. http://dx.doi.org/10.1007/s11390-010-9402-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Hertz, A., and D. de Werra. "Using tabu search techniques for graph coloring." Computing 39, no. 4 (December 1987): 345–51. http://dx.doi.org/10.1007/bf02239976.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Li, Max Z., Karthik Gopalakrishnan, Kristyn Pantoja, and Hamsa Balakrishnan. "Graph Signal Processing Techniques for Analyzing Aviation Disruptions." Transportation Science 55, no. 3 (May 2021): 553–73. http://dx.doi.org/10.1287/trsc.2020.1026.

Full text

Abstract:

Understanding the characteristics of air-traffic delays and disruptions is critical for developing ways to mitigate their significant economic and environmental impacts. Conventional delay-performance metrics reflect only the magnitude of incurred flight delays at airports; in this work, we show that it is also important to characterize the spatial distribution of delays across a network of airports. We analyze graph-supported signals, leveraging techniques from spectral theory and graph-signal processing to compute analytical and simulation-driven bounds for identifying outliers in spatial distribution. We then apply these methods to the case of airport-delay networks and demonstrate the applicability of our methods by analyzing U.S. airport delays from 2008 through 2017. We also perform an airline-specific analysis, deriving insights into the delay dynamics of individual airline subnetworks. Through our analysis, we highlight key differences in delay dynamics between different types of disruptions, ranging from nor’easters and hurricanes to airport outages. We also examine delay interactions between airline subnetworks and the system-wide network and compile an inventory of outlier days that could guide future aviation operations and research. In doing so, we demonstrate how our approach can provide operational insights in an air-transportation setting. Our analysis provides a complementary metric to conventional aviation-delay benchmarks and aids airlines, traffic-flow managers, and transportation-system planners in quantifying off-nominal system performance.

APA, Harvard, Vancouver, ISO, and other styles

31

Wang, Yishu, Ye Yuan, Yuliang Ma, and Guoren Wang. "Time-Dependent Graphs: Definitions, Applications, and Algorithms." Data Science and Engineering 4, no. 4 (September 25, 2019): 352–66. http://dx.doi.org/10.1007/s41019-019-00105-0.

Full text

Abstract:

Abstract A time-dependent graph is, informally speaking, a graph structure dynamically changes with time. In such graphs, the weights associated with edges dynamically change over time, that is, the edges in such graphs are activated by sequences of time-dependent elements. Many real-life scenarios can be better modeled by time-dependent graphs, such as bioinformatics networks, transportation networks, and social networks. In particular, the time-dependent graph is a very broad concept, which is reflected in the related research with many names, including temporal graphs, evolving graphs, time-varying graphs, historical graphs, and so on. Though static graphs have been extensively studied, for their time-dependent generalizations, we are still far from a complete and mature theory of models and algorithms. In this paper, we discuss the definition and topological structure of time-dependent graphs, as well as models for their relationship to dynamic systems. In addition, we review some classic problems on time-dependent graphs, e.g., route planning, social analysis, and subgraph problem (including matching and mining). We also introduce existing time-dependent systems and summarize their advantages and limitations. We try to keep the descriptions consistent as much as possible and we hope the survey can help practitioners to understand existing time-dependent techniques.

APA, Harvard, Vancouver, ISO, and other styles

32

Yang, B., P. Datseris, U. Datta, and J. Kowalski. "An Integrated System for Design of Mechanisms by an Expert System—DOMES: Theory." Journal of Mechanical Design 112, no. 4 (December 1, 1990): 488–93. http://dx.doi.org/10.1115/1.2912636.

Full text

Abstract:

Methodologies have been developed and implemented in LISP and OPS-5 languages which address type synthesis of mechanisms. Graph theory and separation of structure from function concepts have been integrated into an expert system called DOMES (Design Of Mechanism by an Expert System) to effectively implement the following three activities: (1) enumeration of all nonisomorphic labelled graphs; (2) identification of those graphs which satisfy structural constraints; (3) sketching of a mechanism corresponding to a given graph. Developed theories and algorithms are applied to a Robot Gripper design [19] and a Variable Stroke Piston Engine design [16]. The results from these two applications indicate that the automated techniques effectively identify all previously obtained solutions via manual techniques. Additional solutions are also identified and several errors of the manual process are detected. The developed methodologies and software appear to perform a complete and unbiased search of all possible candidate designs and are not prone to the errors of the manual process. Other important features of DOMES are: (1) it can learn and reason, by analogy, about a new design problem based on its experience of the problems previously solved by the system; (2) it has the capability to incrementally expand its knowledge base of rejection criteria by converting into LISP code information obtained through a query-based interactive session with a human designer; (3) it can select the set of rejection criteria relevant to a design problem from its knowledge base of rejection criteria. These procedures could become a powerful tool for design engineers, especially at the conceptual stage of design.

APA, Harvard, Vancouver, ISO, and other styles

33

Beyza, Jesus, Eduardo Garcia-Paricio, and Jose Yusta. "Applying Complex Network Theory to the Vulnerability Assessment of Interdependent Energy Infrastructures." Energies 12, no. 3 (January 29, 2019): 421. http://dx.doi.org/10.3390/en12030421.

Full text

Abstract:

In this paper, we evaluate the use of statistical indexes from graph theory as a possible alternative to power-flow techniques for analyzing cascading failures in coupled electric power and natural gas transmission systems. Both methodologies are applied comparatively to coupled IEEE and natural gas test networks. The cascading failure events are simulated through two strategies of network decomposition: Deliberate attacks on highly connected nodes and random faults. The analysis is performed by simulating successive N-k contingencies in a coupled network, where the network structure changes with the elimination of each node. The suitability of graph-theoretic techniques for assessing the vulnerability of interdependent electric power and natural gas infrastructures is demonstrated.

APA, Harvard, Vancouver, ISO, and other styles

34

Zheng, Yu Ge, and Yan Ming Chang. "On the Edge-Balance Index Sets of the Net Graph C_n²×P_{2_n}(n=0(mod2))." Advanced Materials Research 314-316 (August 2011): 2556–59. http://dx.doi.org/10.4028/www.scientific.net/amr.314-316.2556.

Full text

Abstract:

In this paper, we mainly use the methods and techniques of graph theory and combinatorial mathematics to research the largest edge-balance index of the graph Cn2*P2n(n=0(mod2)), the edge-balance index sets of the graph are discussed, and finally getting the constructive proof about all the edge-balance index sets of Cn2*P2n(n=0(mod2))

APA, Harvard, Vancouver, ISO, and other styles

35

Balasubramanian, Krishnan, and Satya P. Gupta. "Quantum Molecular Dynamics, Topological, Group Theoretical and Graph Theoretical Studies of Protein-Protein Interactions." Current Topics in Medicinal Chemistry 19, no. 6 (May 2, 2019): 426–43. http://dx.doi.org/10.2174/1568026619666190304152704.

Full text

Abstract:

Background: Protein-protein interactions (PPIs) are becoming increasingly important as PPIs form the basis of multiple aggregation-related diseases such as cancer, Creutzfeldt-Jakob, and Alzheimer’s diseases. This mini-review presents hybrid quantum molecular dynamics, quantum chemical, topological, group theoretical, graph theoretical, and docking studies of PPIs. We also show how these theoretical studies facilitate the discovery of some PPI inhibitors of therapeutic importance. Objective: The objective of this review is to present hybrid quantum molecular dynamics, quantum chemical, topological, group theoretical, graph theoretical, and docking studies of PPIs. We also show how these theoretical studies enable the discovery of some PPI inhibitors of therapeutic importance. Methods: This article presents a detailed survey of hybrid quantum dynamics that combines classical and quantum MD for PPIs. The article also surveys various developments pertinent to topological, graph theoretical, group theoretical and docking studies of PPIs and highlight how the methods facilitate the discovery of some PPI inhibitors of therapeutic importance. Results: It is shown that it is important to include higher-level quantum chemical computations for accurate computations of free energies and electrostatics of PPIs and Drugs with PPIs, and thus techniques that combine classical MD tools with quantum MD are preferred choices. Topological, graph theoretical and group theoretical techniques are shown to be important in studying large network of PPIs comprised of over 100,000 proteins where quantum chemical and other techniques are not feasible. Hence, multiple techniques are needed for PPIs. Conclusion: Drug discovery and our understanding of complex PPIs require multifaceted techniques that involve several disciplines such as quantum chemistry, topology, graph theory, knot theory and group theory, thus demonstrating a compelling need for a multi-disciplinary approach to the problem.

APA, Harvard, Vancouver, ISO, and other styles

36

Quilliot, A. "Some Results about Pursuit Games on Metric Spaces Obtained Through Graph Theory Techniques." European Journal of Combinatorics 7, no. 1 (January 1986): 55–66. http://dx.doi.org/10.1016/s0195-6698(86)80017-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Corradini, Andrea, Hartmut Ehrig, Grzegorz Rozenberg, and Gabriele Taentzer. "Introduction." Mathematical Structures in Computer Science 12, no. 2 (April 2002): 111. http://dx.doi.org/10.1017/s0960129501003504.

Full text

Abstract:

This special issue of Mathematical Structures in Computer Science is devoted to the theory and applications of graph transformations. This research area dates back to the early seventies and is based on mathematical techniques from graph theory, algebra, logic and category theory. The theory of graph transformations has become attractive as a modelling and programming paradigm for complex graphical structures in a large variety of areas in computer science and for applications to other fields. During the Joint APPLIGRAPH/GETGRATS Workshop on Graph Transformation Systems (GRATRA 2000) – a satellite of ETAPS 2000 in Berlin – 35 lectures were presented by participants from all over the world. The authors of presentations that stressed the theoretical point of view were invited to submit a full version of their presentation to Mathematical Structures in Computer Science. After a careful refereeing process nine papers have been accepted, seven of which are included in this special issue.The paper by Ehrenfeucht, Petre, Prescott and Rozenberg connects the important new area of DNA computing in vivo to our area of graph transformation. An application of hypergraph constructions to the static analysis of concurrent systems is presented by König, and normal forms for context-free node rewriting hypergraph grammars by Klempien-Hinrichs. The construction of pushout complements for ‘partly total algebras’ generalising attributed graphs is presented by Burmeister, Llabrés and Roselló. Finally, Courcelle and Makowsky present operations on relational structures (generalising different kinds of graphs and hypergraphs) that are compatible with monadic second order logic. Four other accepted papers could not be included in this special issue because of space limitations.They will appear in regular issues of MSCS:— R. Heckel, M. Llabrés, H. Ehrig and F. Orejas: Concurrency and loose semantics of open graph transformation systems.— L. Helouet, C. Jard and B. Caillaud: An event structure based semantics for high-level message sequence charts.— J. Larossa and G. Valiente: Constraint satisfaction algorithms for graph pattern matching.— N. Verlinden and D. Janssens: Algebraic properties for Local Action Systems.We are most grateful to all the referees of these papers, to Olga Runge and Claudia Ermel for technical support, and to Giuseppe Longo and Cambridge University Press for fruitful cooperation in editing this special issue.

APA, Harvard, Vancouver, ISO, and other styles

38

Beyer, Wolfgang, Adam M. Novak, Glenn Hickey, Jeffrey Chan, Vanessa Tan, Benedict Paten, and Daniel R. Zerbino. "Sequence tube maps: making graph genomes intuitive to commuters." Bioinformatics 35, no. 24 (August 1, 2019): 5318–20. http://dx.doi.org/10.1093/bioinformatics/btz597.

Full text

Abstract:

Abstract Motivation Compared to traditional haploid reference genomes, graph genomes are an efficient and compact data structure for storing multiple genomic sequences, for storing polymorphisms or for mapping sequencing reads with greater sensitivity. Further, graphs are well-studied computer science objects that can be efficiently analyzed. However, their adoption in genomic research is slow, in part because of the cognitive difficulty in interpreting graphs. Results We present an intuitive graphical representation for graph genomes that re-uses well-honed techniques developed to display public transport networks, and demonstrate it as a web tool. Availability and implementation Code: https://github.com/vgteam/sequenceTubeMap. Demonstration https://vgteam.github.io/sequenceTubeMap/. Supplementary information Supplementary data are available at Bioinformatics online.

APA, Harvard, Vancouver, ISO, and other styles

39

Li and Yu. "New Bipartite Graph Techniques for Irregular Data Redistribution Scheduling." Algorithms 12, no. 7 (July 16, 2019): 142. http://dx.doi.org/10.3390/a12070142.

Full text

Abstract:

For many parallel and distributed systems, automatic data redistribution improves its locality and increases system performance for various computer problems and applications. In general, an array can be distributed to multiple processing systems by using regular or irregular distributions. Some data distribution adopts BLOCK, CYCLIC, or BLOCK-CYCLIC to specify data array decomposition and distribution. On the other hand, irregular distributions specify a different-size data array distribution according to user-defined commands or procedures. In this work, we propose three bipartite graph problems, including the “maximum edge coloring problem”, the “maximum degree edge coloring problem”, and the “cost-sharing maximum edge coloring problem” to formulate these kinds of distribution problems. Next, we propose an approximation algorithm with a ratio bound of two for the maximum edge coloring problem when the input graph is biplanar. Moreover, we also prove that the “cost-sharing maximum edge coloring problem” is an NP-complete problem even when the input graph is biplanar.

APA, Harvard, Vancouver, ISO, and other styles

40

Alon, Noga, Michael Krivelevich, and Benny Sudakov. "Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions." Combinatorics, Probability and Computing 12, no. 5-6 (November 2003): 477–94. http://dx.doi.org/10.1017/s0963548303005741.

Full text

Abstract:

For a graph H and an integer n, the Turán number is the maximum possible number of edges in a simple graph on n vertices that contains no copy of H. H is r-degenerate if every one of its subgraphs contains a vertex of degree at most r. We prove that, for any fixed bipartite graph H in which all degrees in one colour class are at most r, . This is tight for all values of r and can also be derived from an earlier result of Füredi. We also show that there is an absolute positive constant c such that, for every fixed bipartite r-degenerate graph H, This is motivated by a conjecture of Erdős that asserts that, for every such H, For two graphs G and H, the Ramsey number is the minimum number n such that, in any colouring of the edges of the complete graph on n vertices by red and blue, there is either a red copy of G or a blue copy of H. Erdős conjectured that there is an absolute constant c such that, for any graph G with m edges, . Here we prove this conjecture for bipartite graphs G, and prove that for general graphs G with m edges, for some absolute positive constant c.These results and some related ones are derived from a simple and yet surprisingly powerful lemma, proved, using probabilistic techniques, at the beginning of the paper. This lemma is a refined version of earlier results proved and applied by various researchers including Rödl, Kostochka, Gowers and Sudakov.

APA, Harvard, Vancouver, ISO, and other styles

41

Gu, Geun Ho, Petr Plechac, and Dionisios G. Vlachos. "Thermochemistry of gas-phase and surface species via LASSO-assisted subgraph selection." Reaction Chemistry & Engineering 3, no. 4 (2018): 454–66. http://dx.doi.org/10.1039/c7re00210f.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

KAKOULIS, KONSTANTINOS G., and IOANNIS G. TOLLIS. "A UNIFIED APPROACH TO AUTOMATIC LABEL PLACEMENT." International Journal of Computational Geometry & Applications 13, no. 01 (February 2003): 23–59. http://dx.doi.org/10.1142/s0218195903001062.

Full text

Abstract:

The automatic placement of text or symbol labels corresponding to graphical features is critical in several application areas such as cartography, geographical information systems, and graph drawing. In this paper we present a general framework for solving the problem of assigning text or symbol labels to a set of graphical features in two dimensional drawings or maps. Our approach does not favor the labeling of one type of graphical feature (such as a node, edge, or area) over another. Additionally, the labels are allowed to have arbitrary size and orientation. We also present a fast and simple technique, based on the general framework, for assigning labels to edges of graph drawings. We have implemented our techniques and have performed extensive experimentation on hierarchical and orthogonal drawings of graphs. The resulting label assignments are very practical and indicate the effectiveness of our approach.

APA, Harvard, Vancouver, ISO, and other styles

43

LYONS, RUSSELL. "Identities and Inequalities for Tree Entropy." Combinatorics, Probability and Computing 19, no. 2 (December 15, 2009): 303–13. http://dx.doi.org/10.1017/s0963548309990605.

Full text

Abstract:

The notion of tree entropy was introduced by the author as a normalized limit of the number of spanning trees in finite graphs, but is defined on random infinite rooted graphs. We give some new expressions for tree entropy; one uses Fuglede–Kadison determinants, while another uses effective resistance. We use the latter to prove that tree entropy respects stochastic domination. We also prove that tree entropy is non-negative in the unweighted case, a special case of which establishes Lück's Determinant Conjecture for Cayley-graph Laplacians. We use techniques from the theory of operators affiliated to von Neumann algebras.

APA, Harvard, Vancouver, ISO, and other styles

44

Akwu, Abolape D., and Deborah O. A. Ajayi. "Sunlet Decomposition of Certain Equipartite Graphs." International Journal of Combinatorics 2013 (March 19, 2013): 1–4. http://dx.doi.org/10.1155/2013/907249.

Full text

Abstract:

Let L2n stand for the sunlet graph which is a graph that consists of a cycle and an edge terminating in a vertex of degree one attached to each vertex of cycle Cn. The necessary condition for the equipartite graph Kn+I*K̅m to be decomposed into L2n for n≥2 is that the order of L2n must divide n2m2/2, the order of Kn+I*K̅m. In this work, we show that this condition is sufficient for the decomposition. The proofs are constructive using graph theory techniques.

APA, Harvard, Vancouver, ISO, and other styles

45

Yaqoob, Naveed, Muhammad Gulistan, Seifedine Kadry, and Hafiz Abdul Wahab. "Complex Intuitionistic Fuzzy Graphs with Application in Cellular Network Provider Companies." Mathematics 7, no. 1 (January 1, 2019): 35. http://dx.doi.org/10.3390/math7010035.

Full text

Abstract:

In recent years, a mathematical approach of blending different aspects is on the way, which as a result gives a more generalized approach. Following the above mathematical approach, we combine two very powerful techniques, namely complex intuitionistic fuzzy sets and graph theory, and introduce the notion of complex intuitionistic fuzzy graphs. Then, we introduce certain notions including union, join and composition of complex intuitionistic fuzzy graphs, through which one can easily manipulate the complex intuitionistic fuzzy graphs in decision making problems. We elucidate these operations with some examples. We also describe the homomorphisms of complex intuitionistic fuzzy graphs. Finally, we provide an application in cellular network provider companies for the testing of our approach.

APA, Harvard, Vancouver, ISO, and other styles

46

Younis, Mudasir, Deepak Singh, Stojan Radenovic, and Mohammad Imdad. "Convergence theorems for generalized contractions and applications." Filomat 34, no. 3 (2020): 945–64. http://dx.doi.org/10.2298/fil2003945y.

Full text

Abstract:

The principal results in this article deal with the existence of fixed points of a new class of generalized F-contraction. In our approach, by visualizing some non-trivial examples we will obtain better geometrical interpretation. Our main results substantially improve the theory of F-contraction mappings and the related fixed point theorems. In section-4, application to graph theory is entrusted and proved results are endorsed by an example through graph. The presented new techniques give the possibility to justify the existence problems of the solutions for some class of integral equations. For the future aspects of our study, an open problem is suggested regarding discretized population balance model, whose solution may be derived from the established techniques.

APA, Harvard, Vancouver, ISO, and other styles

47

Mitchell, Eleanor M., Peter J. Artymiuk, David W. Rice, and Peter Willett. "Use of techniques derived from graph theory to compare secondary structure motifs in proteins." Journal of Molecular Biology 212, no. 1 (March 1990): 151–66. http://dx.doi.org/10.1016/0022-2836(90)90312-a.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Chen, Xiao Mei, Xiao Feng Meng, and Guo Hua Wang. "Optimum Test Point Selection Based on MADM for Analog Fault Dictionary Techniques." Applied Mechanics and Materials 48-49 (February 2011): 807–12. http://dx.doi.org/10.4028/www.scientific.net/amm.48-49.807.

Full text

Abstract:

a new graph-search algorithm based on multi-attribute decision making (MADM) is proposed. Firstly, A* algorithm is used for graph-search, but when cost functions of two nodes are equal, three attributes describing a node are introduced. Secondly, a multi-attribute decision based on maximum deviation principle is used for nodes evaluation in order to select the best node for expanding. The proposed algorithm could overcome deviation brought by node evaluation based on information theory metrics only, which results in high accuracy. The outcome of simulation verification at the end of this paper manifests that this algorithm has excellent accuracy as the exhaustive algorithm, and is more quickly for large scale computation.

APA, Harvard, Vancouver, ISO, and other styles

49

Cai, Hongyun, Vincent W. Zheng, and Kevin Chen-Chuan Chang. "A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications." IEEE Transactions on Knowledge and Data Engineering 30, no. 9 (September 1, 2018): 1616–37. http://dx.doi.org/10.1109/tkde.2018.2807452.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

James, Jinto, K. A. Germina, and P. Shaini. "Learning graphs and 1-uniform dcsl graphs." Discrete Mathematics, Algorithms and Applications 09, no. 04 (August 2017): 1750046. http://dx.doi.org/10.1142/s179383091750046x.

Full text

Abstract:

A distance compatible set labeling (dcsl) of a connected graph [Formula: see text] is an injective set assignment [Formula: see text] [Formula: see text] being a non-empty ground set, such that the corresponding induced function [Formula: see text] given by [Formula: see text] satisfies [Formula: see text] for every pair of distinct vertices [Formula: see text] where [Formula: see text] denotes the path distance between [Formula: see text] and [Formula: see text] and [Formula: see text] is a constant, not necessarily an integer, depending on the pair of vertices [Formula: see text] chosen. A dcsl [Formula: see text] of [Formula: see text] is [Formula: see text]-uniform if all the constants of proportionality with respect to [Formula: see text] are equal to [Formula: see text] and if [Formula: see text] admits such a dcsl then [Formula: see text] is called a [Formula: see text]-uniform dcsl graph. The family [Formula: see text] is well-graded family, if there is a tight path between any two of its distinct sets. A learning graph is an [Formula: see text]-induced graph of a learning space. In this paper, we initiate a study on subgraphs of 1-uniform graphs which lead to the study of Knowledge Structures, Learning Spaces and Union-closed conjecture using graph theory techniques.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Graph theory techniques'

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