Journal articles: 'Search in graphs AND'

1

Itzhakov, Avraham, and Michael Codish. "Incremental Symmetry Breaking Constraints for Graph Search Problems." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 02 (2020): 1536–43. http://dx.doi.org/10.1609/aaai.v34i02.5513.

Full text

Abstract:

This paper introduces incremental symmetry breaking constraints for graph search problems which are complete and compact. We show that these constraints can be computed incrementally: A symmetry breaking constraint for order n graphs can be extended to one for order n + 1 graphs. Moreover, these constraints induce a special property on their canonical solutions: An order n canonical graph contains a canonical subgraph on the first k vertices for every 1 ≤ k ≤ n. This facilitates a “generate and extend” paradigm for parallel graph search problem solving: To solve a graph search problem φ on order n graphs, first generate the canonical graphs of some order k < n. Then, compute canonical solutions for φ by extending, in parallel, each canonical order k graph together with suitable symmetry breaking constraints. The contribution is that the proposed symmetry breaking constraints enable us to extend the order k canonical graphs to order n canonical solutions. We demonstrate our approach through its application on two hard graph search problems.

APA, Harvard, Vancouver, ISO, and other styles

2

Yang, Jianye, Wu Yao, and Wenjie Zhang. "Keyword Search on Large Graphs: A Survey." Data Science and Engineering 6, no. 2 (2021): 142–62. http://dx.doi.org/10.1007/s41019-021-00154-4.

Full text

Abstract:

AbstractWith the prevalence of Internet access and online services, various big graphs are generated in many real applications (e.g., online social networks and knowledge graphs). An important task on analyzing and mining these graphs is keyword search. Essentially, given a graph G and query Q associated with a set of keywords, the keyword search aims to find a substructure (e.g., rooted tree or subgraph) S in G such that nodes in S collectively cover part of or all keywords in Q, and in the meanwhile, S is optimal on some user specified semantics. Keyword search on graphs can be applied in many real-life applications, such as point-of-interests recommendation and web search facility. In spite of the great importance of graph keyword search, we, however, notice that the latest survey on this topic is far out of date. Consequently, there is prompt need to conduct a comprehensive survey in this research direction. Motivated by this, in this survey, we systematically review graph keyword search studies by classifying the existing works into different categories according to the specific problem definition. This survey aims to provide the researchers a comprehensive understanding of existing graph keyword search solutions.

APA, Harvard, Vancouver, ISO, and other styles

3

Beamer, Scott, Krste Asanović, and David Patterson. "Direction-Optimizing Breadth-First Search." Scientific Programming 21, no. 3-4 (2013): 137–48. http://dx.doi.org/10.1155/2013/702694.

Full text

Abstract:

Breadth-First Search is an important kernel used by many graph-processing applications. In many of these emerging applications of BFS, such as analyzing social networks, the input graphs are low-diameter and scale-free. We propose a hybrid approach that is advantageous for low-diameter graphs, which combines a conventional top-down algorithm along with a novel bottom-up algorithm. The bottom-up algorithm can dramatically reduce the number of edges examined, which in turn accelerates the search as a whole. On a multi-socket server, our hybrid approach demonstrates speedups of 3.3–7.8 on a range of standard synthetic graphs and speedups of 2.4–4.6 on graphs from real social networks when compared to a strong baseline. We also typically double the performance of prior leading shared memory (multicore and GPU) implementations.

APA, Harvard, Vancouver, ISO, and other styles

4

Kargar, Mehdi, and Aijun An. "Keyword search in graphs." Proceedings of the VLDB Endowment 4, no. 10 (2011): 681–92. http://dx.doi.org/10.14778/2021017.2021025.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Lunegov, S. V., and N. N. Petrov. "Search Problems on Graphs." IFAC Proceedings Volumes 34, no. 6 (2001): 969–71. http://dx.doi.org/10.1016/s1474-6670(17)35307-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Aigner, M. "Search problems on graphs." Discrete Applied Mathematics 14, no. 3 (1986): 215–30. http://dx.doi.org/10.1016/0166-218x(86)90026-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Zainullina, R. "Automatic Graph Generation for E-learning Systems." Bulletin of Science and Practice 7, no. 6 (2021): 12–16. http://dx.doi.org/10.33619/2414-2948/67/01.

Full text

Abstract:

The subject of the research is one of the ways of updating modern training systems for solving problems of graph theory, namely, automatic generation of graphs. This approach will reduce the load on the training system database and generate tasks for the user in real-time without updating the bank of tasks. In the course of the work, the advantages and disadvantages of this approach were identified. The most suitable method for the implementation of the research was chosen to represent graphs in electronic computers. The requirements for generated graphs and possible ways of implementing these requirements are identified and substantiated. Namely: in the implemented program, simple connected undirected graphs will be generated. We considered an important detail in working with graphs — graph traversal using the “Depth (width) search” algorithm, which in this task is used to check the graph for connectivity. The result of the work is presented — a software implementation of the graph generation algorithm in the C# programming language. In it, graphs are represented by an adjacency list, generated randomly, and checked for connectivity using the DFS (Depth First Search) function. DFS is a software implementation of the Depth First Search algorithm.

APA, Harvard, Vancouver, ISO, and other styles

8

Burkhardt, Paul. "Optimal Algebraic Breadth-First Search for Sparse Graphs." ACM Transactions on Knowledge Discovery from Data 15, no. 5 (2021): 1–19. http://dx.doi.org/10.1145/3446216.

Full text

Abstract:

There has been a rise in the popularity of algebraic methods for graph algorithms given the development of the GraphBLAS library and other sparse matrix methods. An exemplar for these approaches is Breadth-First Search (BFS). The algebraic BFS algorithm is simply a recurrence of matrix-vector multiplications with the n × n adjacency matrix, but the many redundant operations over nonzeros ultimately lead to suboptimal performance. Therefore an optimal algebraic BFS should be of keen interest especially if it is easily integrated with existing matrix methods. Current methods, notably in the GraphBLAS, use a Sparse Matrix masked-Sparse Vector multiplication in which the input vector is kept in a sparse representation in each step of the BFS, and nonzeros in the vector are masked in subsequent steps. This has been an area of recent research in GraphBLAS and other libraries. While in theory, these masking methods are asymptotically optimal on sparse graphs, many add work that leads to suboptimal runtime. We give a new optimal, algebraic BFS for sparse graphs, thus closing a gap in the literature. Our method multiplies progressively smaller submatrices of the adjacency matrix at each step. Let n and m refer to the number of vertices and edges, respectively. On a sparse graph, our method takes O ( n ) algebraic operations as opposed to O ( m ) operations needed by theoretically optimal sparse matrix approaches. Thus, for sparse graphs, it matches the bounds of the best-known sequential algorithm, and on a Parallel Random Access Machine, it is work-optimal. Our result holds for both directed and undirected graphs. Compared to a leading GraphBLAS library, our method achieves up to 24x faster sequential time, and for parallel computation, it can be 17x faster on large graphs and 12x faster on large-diameter graphs.

APA, Harvard, Vancouver, ISO, and other styles

9

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

10

Wang, Yiyuan, Shaowei Cai, Shiwei Pan, Ximing Li, and Monghao Yin. "Reduction and Local Search for Weighted Graph Coloring Problem." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 03 (2020): 2433–41. http://dx.doi.org/10.1609/aaai.v34i03.5624.

Full text

Abstract:

The weighted graph coloring problem (WGCP) is an important extension of the graph coloring problem (GCP) with wide applications. Compared to GCP, where numerous methods have been developed and even massive graphs with millions of vertices can be solved well, fewer works have been done for WGCP, and no solution is available for solving WGCP for massive graphs. This paper explores techniques for solving WGCP, including a lower bound and a reduction rule based on clique sampling, and a local search algorithm based on two selection rules and a new variant of configuration checking. This results in our algorithm RedLS (Reduction plus Local Search). Experiments are conducted to compare RedLS with the state-of-the-art algorithms on massive graphs as well as conventional benchmarks studied in previous works. RedLS exhibits very good performance and robustness. It significantly outperforms previous algorithms on all benchmarks.

APA, Harvard, Vancouver, ISO, and other styles

11

CUCKA, PETER, NATHAN S. NETANYAHU, and AZRIEL ROSENFELD. "LEARNING IN NAVIGATION: GOAL FINDING IN GRAPHS." International Journal of Pattern Recognition and Artificial Intelligence 10, no. 05 (1996): 429–46. http://dx.doi.org/10.1142/s0218001496000281.

Full text

Abstract:

A robotic agent operating in an unknown and complex environment may employ a search strategy of some kind to perform a navigational task such as reaching a given goal. In the process of performing the task, the agent can attempt to discover characteristics of its environment that enable it to choose a more efficient search strategy for that environment. If the agent is able to do this, we can say that it has "learned to navigate" — i.e., to improve its navigational performance. This paper describes how an agent can learn to improve its goal-finding performance in a class of discrete spaces, represented by graphs embedded in the plane. We compare several basic search strategies on two different classes of "random" graphs and show how information collected during the traversal of a graph can be used to classify the graph, thus allowing the agent to choose the search strategy best suited for that graph.

APA, Harvard, Vancouver, ISO, and other styles

12

Fakas, Georgios J., and Zhi Cai. "Object summaries for keyword search." Encyclopedia with Semantic Computing and Robotic Intelligence 02, no. 02 (2018): 1750002. http://dx.doi.org/10.1142/s2529737617500022.

Full text

Abstract:

The abundance and ubiquity of graphs (e.g., semantic knowledge graphs, such as Google’s knowledge graph, DBpedia; online social networks such as Google[Formula: see text], Facebook; bibliographic graphs such as DBLP, etc.) necessitates the effective and efficient search over them. Thus, we propose a novel keyword search paradigm, where the result of a search is an Object Summary (OS). More precisely, given a set of keywords that can identify a Data Subject (DS), our paradigm produces a set of OSs as results. An OS is a tree structure rooted at the DS node (i.e., a node containing the keywords) with surrounding nodes that summarize all data held on the graph about the DS. An OS can potentially be very large in size and therefore unfriendly for users who wish to view synoptic information about the data subject. Thus, we investigate the effective and efficient retrieval of concise and informative OS snippets (denoted as size-[Formula: see text] OSs). A size-[Formula: see text] OS is a partial OS containing [Formula: see text] nodes such that the summation of their importance scores results in the maximum possible total score. However, the set of nodes that maximize the total importance score may result in an uninformative size-[Formula: see text] OSs, as very important nodes may be repeated in it, dominating other representative information. In view of this limitation, we investigate the effective and efficient generation of two novel types of OS snippets, i.e., diverse and proportional size-[Formula: see text] OSs, denoted as DSize-[Formula: see text] and PSize-[Formula: see text] OSs. Namely, besides the importance of each node, we also consider its pairwise relevance (similarity) to the other nodes in the OS and the snippet. We conduct an extensive evaluation on two real graphs (DBLP and Google[Formula: see text]). We verify effectiveness by collecting user feedback, e.g., by asking DBLP authors (i.e., the DSs themselves) to evaluate our results. In addition, we verify the efficiency of our algorithms and evaluate quality of the snippets that they produce.

APA, Harvard, Vancouver, ISO, and other styles

13

Rücker, Gerta, Christoph Rücker, and Ivan Gutman. "On Kites, Comets, and Stars. Sums of Eigenvector Coefficients in (Molecular) Graphs." Zeitschrift für Naturforschung A 57, no. 3-4 (2002): 143–53. http://dx.doi.org/10.1515/zna-2002-3-406.

Full text

Abstract:

Two graph invariants were encountered that form the link between (molecular) walk counts and eigenvalues of graph adjacency matrices. In particular, the absolute value of the sum of coefficients of the first or principal (normalized) eigenvector, s1, and the analogous quantity sn, pertaining to the last eigenvector, appear in equations describing some limits (for infinitely long walks) of relative frequencies of several walk counts. Quantity s1 is interpreted as a measure of mixedness of a graph, and sn, which plays a role for bipartite graphs only, is interpreted as a measure of the imbalance of a bipartite graph. Consequently, sn is maximal for star graphs, while the minimal value of sn is zero. Mixedness s1 is maximal for regular graphs. Minimal values of s1 were found by exhaustive computer search within the sample of all simple connected undirected n-vertex graphs, n≤10: They are encountered among graphs called kites. Within the special sample of tree graphs (searched for n≤20) so-called double snakes have maximal s1, while the trees with minimal s1 are so-called comets. The behaviour of stars and double snakes can be described by exact equations, while approximate equations for s1 of kites and comets could be derived that are fully compatible with and allow to predict some pecularities of the results of the computer search. Finally, the discriminating power of s1, determined within trees and 4-trees (alkanes), was found to be high.

APA, Harvard, Vancouver, ISO, and other styles

14

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 (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

15

Dinh, H., and A. Russell. "Quantum and randomized lower bounds for local search on vertex-transitive graphs." Quantum Information and Computation 10, no. 7&8 (2010): 638–52. http://dx.doi.org/10.26421/qic10.7-8-5.

Full text

Abstract:

We study the problem of \emph{local search} on a graph. Given a real-valued black-box function $f$ on the graph's vertices, this is the problem of determining a local minimum of $f$---a vertex $v$ for which $f(v)$ is no more than $f$ evaluated at any of $v$'s neighbors. In 1983, Aldous gave the first strong lower bounds for the problem, showing that any randomized algorithm requires $\Omega(2^{n/2 - o(n)} )$ queries to determine a local minima on the $n$-dimensional hypercube. The next major step forward was not until 2004 when Aaronson, introducing a new method for query complexity bounds, both strengthened this lower bound to $\Omega(2^{n/2}/n^2)$ and gave an analogous lower bound on the quantum query complexity. While these bounds are very strong, they are known only for narrow families of graphs (hypercubes and grids). We show how to generalize Aaronson's techniques in order to give randomized (and quantum) lower bounds on the query complexity of local search for the family of vertex-transitive graphs. In particular, we show that for any vertex-transitive graph $G$ of $N$ vertices and diameter $d$, the randomized and quantum query complexities for local search on $G$ are $\Omega\left({\sqrt{N}}/{d\log N}\right)$ and $\Omega\left({\sqrt[4]{N}}/{\sqrt{d\log N}}\right)$, respectively.

APA, Harvard, Vancouver, ISO, and other styles

16

Liu, Ziyang, Chong Wang, and Yi Chen. "Keyword Search on Temporal Graphs." IEEE Transactions on Knowledge and Data Engineering 29, no. 8 (2017): 1667–80. http://dx.doi.org/10.1109/tkde.2017.2690637.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Huang, Xin, Laks V. S. Lakshmanan, and Jianliang Xu. "Community Search over Big Graphs." Synthesis Lectures on Data Management 14, no. 6 (2019): 1–206. http://dx.doi.org/10.2200/s00928ed1v01y201906dtm061.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Cheng, Gong. "Relationship search over knowledge graphs." ACM SIGWEB Newsletter, Summer 2020 (July 27, 2020): 1–8. http://dx.doi.org/10.1145/3409481.3409484.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Likhachev, Maxim, Dave Ferguson, Geoff Gordon, Anthony Stentz, and Sebastian Thrun. "Anytime search in dynamic graphs." Artificial Intelligence 172, no. 14 (2008): 1613–43. http://dx.doi.org/10.1016/j.artint.2007.11.009.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Deligkas, Argyrios, George B. Mertzios, and Paul G. Spirakis. "Binary Search in Graphs Revisited." Algorithmica 81, no. 5 (2018): 1757–80. http://dx.doi.org/10.1007/s00453-018-0501-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Antalan, John Rafael Macalisang, and Francis Joseph Campena. "A Breadth-first Search Tree Construction for Multiplicative Circulant Graphs." European Journal of Pure and Applied Mathematics 14, no. 1 (2021): 248–64. http://dx.doi.org/10.29020/nybg.ejpam.v14i1.3884.

Full text

Abstract:

In this paper, we give a recursive method in constructing a breadth-first search tree for multiplicative circulant graphs of order power of odd. We then use the proposed construction in reproving some results concerning multiplicative circulant graph's diameter, average distance and distance spectral radius. We also determine the graph's Wiener index, vertex-forwarding index, and a bound for its edge-forwarding index. Finally, we discuss some possible research works in which the proposed construction can be applied.

APA, Harvard, Vancouver, ISO, and other styles

22

Yamada, Masataka, and Akihiro Inokuchi. "Similar Supergraph Search Based on Graph Edit Distance." Algorithms 14, no. 8 (2021): 225. http://dx.doi.org/10.3390/a14080225.

Full text

Abstract:

Subgraph and supergraph search methods are promising techniques for the development of new drugs. For example, the chemical structure of favipiravir—an antiviral treatment for influenza—resembles the structure of some components of RNA. Represented as graphs, such compounds are similar to a subgraph of favipiravir. However, the existing supergraph search methods can only discover compounds that match exactly. We propose a novel problem, called similar supergraph search, and design an efficient algorithm to solve it. The problem is to identify all graphs in a database that are similar to any subgraph of a query graph, where similarity is defined as edit distance. Our algorithm represents the set of candidate subgraphs by a code tree, which it uses to efficiently compute edit distance. With a distance threshold of zero, our algorithm is equivalent to an existing efficient algorithm for exact supergraph search. Our experiments show that the computation time increased exponentially as the distance threshold increased, but increased sublinearly with the number of graphs in the database.

APA, Harvard, Vancouver, ISO, and other styles

23

Tuite, James, and Grahame Erskine. "On Total Regularity of Mixed Graphs with Order Close to the Moore Bound." Graphs and Combinatorics 35, no. 6 (2019): 1253–72. http://dx.doi.org/10.1007/s00373-019-02114-2.

Full text

Abstract:

Abstract The undirected degree/diameter and degree/girth problems and their directed analogues have been studied for many decades in the search for efficient network topologies. Recently such questions have received much attention in the setting of mixed graphs, i.e. networks that admit both undirected edges and directed arcs. The degree/diameter problem for mixed graphs asks for the largest possible order of a network with diameter k, maximum undirected degree $$\le r$$≤r and maximum directed out-degree $$\le z$$≤z. Similarly one can search for the smallest possible k-geodetic mixed graphs with minimum undirected degree $$\ge r$$≥r and minimum directed out-degree $$\ge z$$≥z. A simple counting argument reveals the existence of a natural bound, the Moore bound, on the order of such graphs; a graph that meets this limit is a mixed Moore graph. Mixed Moore graphs can exist only for $$k = 2$$k=2 and even in this case it is known that they are extremely rare. It is therefore of interest to search for graphs with order one away from the Moore bound. Such graphs must be out-regular; a much more difficult question is whether they must be totally regular. For $$k = 2$$k=2, we answer this question in the affirmative, thereby resolving an open problem stated in a recent paper of López and Miret. We also present partial results for larger k. We finally put these results to practical use by proving the uniqueness of a 2-geodetic mixed graph with order exceeding the Moore bound by one.

APA, Harvard, Vancouver, ISO, and other styles

24

Merz, Peter, and Bernd Freisleben. "Fitness Landscapes, Memetic Algorithms, and Greedy Operators for Graph Bipartitioning." Evolutionary Computation 8, no. 1 (2000): 61–91. http://dx.doi.org/10.1162/106365600568103.

Full text

Abstract:

The fitness landscape of the graph bipartitioning problem is investigated by performing a search space analysis for several types of graphs. The analysis shows that the structure of the search space is significantly different for the types of instances studied. Moreover, with increasing epistasis, the amount of gene interactions in the representation of a solution in an evolutionary algorithm, the number of local minima for one type of instance decreases and, thus, the search becomes easier. We suggest that other characteristics besides high epistasis might have greater influence on the hardness of a problem. To understand these characteristics, the notion of a dependency graph describing gene interactions is introduced. In particular, the local structure and the regularity of the dependency graph seems to be important for the performance of an algorithm, and in fact, algorithms that exploit these properties perform significantly better than others which do not. It will be shown that a simple hybrid multi-start local search exploiting locality in the structure of the graphs is able to find optimum or near optimum solutions very quickly. However, if the problem size increases or the graphs become unstructured, a memetic algorithm (a genetic algorithm incorporating local search) is shown to be much more effective.

APA, Harvard, Vancouver, ISO, and other styles

25

Molga, Karol, Piotr Dittwald, and Bartosz A. Grzybowski. "Computational design of syntheses leading to compound libraries or isotopically labelled targets." Chemical Science 10, no. 40 (2019): 9219–32. http://dx.doi.org/10.1039/c9sc02678a.

Full text

Abstract:

Network-search routines over large graphs of retrosynthetic scenarios are adapted to multi-target design operating on one common search graph enabling design of syntheses of compound libraries or isotopically labelled targets.

APA, Harvard, Vancouver, ISO, and other styles

26

Paris, Matteo G. A., Claudia Benedetti, and Stefano Olivares. "Improving Quantum Search on Simple Graphs by Pretty Good Structured Oracles." Symmetry 13, no. 1 (2021): 96. http://dx.doi.org/10.3390/sym13010096.

Full text

Abstract:

Quantum search algorithms provide a way to speed up combinatorial search, and have found several applications in modern quantum technology. In particular, spatial search on graphs, based on continuous-time quantum walks (CTQW), represents a promising platform for the implementation of quantum search in condensed matter systems. CTQW-based algorithms, however, work exactly on complete graphs, while they are known to perform poorly on realistic graphs with low connectivity. In this paper, we put forward an alternative search algorithm, based on structuring the oracle operator, which allows one to improve the localization properties of the walker by tuning only the on-site energies of the graph, i.e., without altering its topology. As such, the proposed algorithm is suitable for implementation in systems with low connectivity, e.g., rings of quantum dots or superconducting circuits. Oracle parameters are determined by Hamiltonian constraints, without the need for numerical optimization.

APA, Harvard, Vancouver, ISO, and other styles

27

Paris, Matteo G. A., Claudia Benedetti, and Stefano Olivares. "Improving Quantum Search on Simple Graphs by Pretty Good Structured Oracles." Symmetry 13, no. 1 (2021): 96. http://dx.doi.org/10.3390/sym13010096.

Full text

Abstract:

Quantum search algorithms provide a way to speed up combinatorial search, and have found several applications in modern quantum technology. In particular, spatial search on graphs, based on continuous-time quantum walks (CTQW), represents a promising platform for the implementation of quantum search in condensed matter systems. CTQW-based algorithms, however, work exactly on complete graphs, while they are known to perform poorly on realistic graphs with low connectivity. In this paper, we put forward an alternative search algorithm, based on structuring the oracle operator, which allows one to improve the localization properties of the walker by tuning only the on-site energies of the graph, i.e., without altering its topology. As such, the proposed algorithm is suitable for implementation in systems with low connectivity, e.g., rings of quantum dots or superconducting circuits. Oracle parameters are determined by Hamiltonian constraints, without the need for numerical optimization.

APA, Harvard, Vancouver, ISO, and other styles

28

Cheng, Bo. "Research on the Search Strategy of Complex Network Based on Breadth-First." Applied Mechanics and Materials 556-562 (May 2014): 5348–51. http://dx.doi.org/10.4028/www.scientific.net/amm.556-562.5348.

Full text

Abstract:

As the computer science is developing rapidly, the search of technology of graphs has emerged in logic, linguistics, chemistry, electronics and some other fields of science. Especially with the rapid development of network technology as well as the appearance of parallel computer, parallel processing is brought into an unprecedented prosperity. And graphs traversal also starts playing a vital role. Breadth-first-search is a fundamental problem of graph theory as well as a heated problem. The parallelization of breadth-first-search has been a tough problem yet to be solved.

APA, Harvard, Vancouver, ISO, and other styles

29

J., Abhijith, and Apoorva Patel. "Spatial search using flip-flop quantum walk." Quantum Information and Computation 18, no. 15&16 (2018): 1295–331. http://dx.doi.org/10.26421/qic18.15-16-3.

Full text

Abstract:

We analyse the eigenvalue and eigenvector structure of the flip-flop quantum walk on regular graphs, explicitly demonstrating how it is quadratically faster than the classical random walk. Then we use it in a controlled spatial search algorithm with multiple target states, and determine the oracle complexity as a function of the spectral gap and the number of target states. The oracle complexity is optimal as a function of the graph size and the number of target states, when the spectral gap of the adjacency matrix is $\Theta(1)$. It is also optimal for spatial search on D>4 dimensional hypercubic lattices. Otherwise it matches the best result available in the literature, with a much simpler algorithm. Our results also yield bounds on the classical hitting time of random walks on regular graphs, which may be of independent interest.

APA, Harvard, Vancouver, ISO, and other styles

30

Seo, Kwangwon, Jinhyun Ahn, and Dong-Hyuk Im. "Optimization of Shortest-Path Search on RDBMS-Based Graphs." ISPRS International Journal of Geo-Information 8, no. 12 (2019): 550. http://dx.doi.org/10.3390/ijgi8120550.

Full text

Abstract:

Calculation of the shortest path between two nodes in a graph is a popular operation used in graph queries in applications such as map information systems, social networking services, and biotechnology. Recent shortest-path search techniques based on graphs stored in relational databases are able to calculate the shortest path efficiently, even in large data using frontier-expand-merge operations. However, previous approaches used a sequential bidirectional search method that causes a bottleneck, thus degrading performance. The repeated use of an aggregate SQL function also degrades performance. This paper proposes a parallel bi-directional search method using multithreading. In addition, an efficient optimization method is proposed that uses B-tree indexing instead of an aggregate SQL function. Various experiments using synthetic and real data reveal that the proposed optimization technique performs more efficiently than conventional methods. As the size of data in practical applications continues to grow, these optimizations will enable the shortest path in a graph to be found quickly and accurately.

APA, Harvard, Vancouver, ISO, and other styles

31

Grabowecky, Marcia, Stacey Parrott, Emmanuel Guzman-Martinez, Laura Ortega, and Satoru Suzuki. "Auditory–visual, positional, and semantic effects in visual extraction of slope." Seeing and Perceiving 25 (2012): 196. http://dx.doi.org/10.1163/187847612x648251.

Full text

Abstract:

Extracting slopes from arrays of visual features is crucial for interpreting graphs. To understand broader influences on slope perception, we investigated the effects of concurrent sounds, of relative graph location, and of semantic priming on a visual search task in which observers searched for a graph with a positive or negative slope. Four bar graphs or scatter plots were simultaneously presented in separate quadrants of a visual display. Participants pressed a key as quickly as possible if one of the graphs displayed the target slope and otherwise refrained from response. A concurrently presented ascending pitch slowed responses to negative-slope targets, and concurrently presented descending pitch slowed responses to positive-slope targets, indicating crossmodal interference. This interference was eliminated when the sounds were presented 200 ms before the graphs, consistent with crossmodal interaction rather than response bias. Positive slopes were detected slowest in the upper-left quadrant whereas negative slopes were detected slowest in the upper-right quadrant, suggesting that slope detection is impeded when a graph is placed inconsistently with a mental number-line representation (negative values on the left and positive values on the right). Finally, positive slopes were detected faster when the search display was immediately preceded by a briefly flashed word ‘uphill’ compared to the word ‘downhill’ (and the converse for negative slopes), indicating a semantic priming effect, but this was observed only for scatter plots (the stimulus specificity precluding response bias). In summary, perception of visual slope is systematically influenced by auditory signals, by location of graphs, and by semantic priming.

APA, Harvard, Vancouver, ISO, and other styles

32

Luccio, Flaminia L. "Contiguous Search Problem in Sierpiński Graphs." Theory of Computing Systems 44, no. 2 (2008): 186–204. http://dx.doi.org/10.1007/s00224-008-9116-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Caporossi, Gilles, Ivan Gutman, and Pierre Hansen. "Variable neighborhood search for extremal graphs." Computers & Chemistry 23, no. 5 (1999): 469–77. http://dx.doi.org/10.1016/s0097-8485(99)00031-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Lian, Xiang, Lei Chen, and Zi Huang. "Keyword Search Over Probabilistic RDF Graphs." IEEE Transactions on Knowledge and Data Engineering 27, no. 5 (2015): 1246–60. http://dx.doi.org/10.1109/tkde.2014.2365791.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Wong, Thomas G. "Quantum walk search on Johnson graphs." Journal of Physics A: Mathematical and Theoretical 49, no. 19 (2016): 195303. http://dx.doi.org/10.1088/1751-8113/49/19/195303.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Arcaute, Esteban, Ning Chen, Ravi Kumar, et al. "Deterministic Decentralized Search in Random Graphs." Internet Mathematics 5, no. 1-2 (2008): 141–54. http://dx.doi.org/10.1080/15427951.2008.10129298.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Andreae, Thomas. "A ternary search problem on graphs." Discrete Applied Mathematics 23, no. 1 (1989): 1–10. http://dx.doi.org/10.1016/0166-218x(89)90030-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Franzkeit, Reinhard. "A binary search problem on graphs." Discrete Applied Mathematics 36, no. 1 (1992): 83–86. http://dx.doi.org/10.1016/0166-218x(92)90207-q.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Koh, K. M., and K. L. Teo. "The search for chromatically unique graphs." Graphs and Combinatorics 6, no. 3 (1990): 259–85. http://dx.doi.org/10.1007/bf01787578.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Ivakin, Y., and S. Potapichev. "ALGORITHM OF BIOGRAPHICAL HYPOTHESES TESTING BASED ON GEOCHRONOLOGICAL TRACKING." Telecom IT 7, no. 1 (2019): 60–74. http://dx.doi.org/10.31854/2307-1303-2019-7-1-60-74.

Full text

Abstract:

Research subject. Information technology of the geochronological tracking is an assembly of processes that accumulate and integrate data about geographic relocation of historical figures for a given time interval and represent the results as a generalizing graph in GIS. Method. Hypotheses on the stable tendencies in migration could be represented as the above graph’s sub-graphs. Such tendencies testing would be reduced to the search and evaluation of the statistical significance for the matching graphs’ isomorphism. Full-featured development of computer interpretation of the graph theory methods based on geochronological tracking provides new quality of historical research using modern GIS-tools. Practical relevance. Namely, researcher can use the quantitative methods of the corresponding logical-analytical apparatus. The proposed paper deals with a consideration of qualitatively new possibilities of such an approach and the corresponding algorithmic apparatus.

APA, Harvard, Vancouver, ISO, and other styles

41

Lanel, G. H. J., H. K. Pallage, J. K. Ratnayake, S. Thevasha, and B. A. K. Welihinda. "A survey on Hamiltonicity in Cayley graphs and digraphs on different groups." Discrete Mathematics, Algorithms and Applications 11, no. 05 (2019): 1930002. http://dx.doi.org/10.1142/s1793830919300029.

Full text

Abstract:

Lovász had posed a question stating whether every connected, vertex-transitive graph has a Hamilton path in 1969. There is a growing interest in solving this longstanding problem and still it remains widely open. In fact, it was known that only five vertex-transitive graphs exist without a Hamiltonian cycle which do not belong to Cayley graphs. A Cayley graph is the subclass of vertex-transitive graph, and in view of the Lovász conjecture, the attention has focused more toward the Hamiltonicity of Cayley graphs. This survey will describe the current status of the search for Hamiltonian cycles and paths in Cayley graphs and digraphs on different groups, and discuss the future direction regarding famous conjecture.

APA, Harvard, Vancouver, ISO, and other styles

42

Liu, Shunyi. "Generalized Permanental Polynomials of Graphs." Symmetry 11, no. 2 (2019): 242. http://dx.doi.org/10.3390/sym11020242.

Full text

Abstract:

The search for complete graph invariants is an important problem in graph theory and computer science. Two networks with a different structure can be distinguished from each other by complete graph invariants. In order to find a complete graph invariant, we introduce the generalized permanental polynomials of graphs. Let G be a graph with adjacency matrix A ( G ) and degree matrix D ( G ) . The generalized permanental polynomial of G is defined by P G ( x , μ ) = per ( x I − ( A ( G ) − μ D ( G ) ) ) . In this paper, we compute the generalized permanental polynomials for all graphs on at most 10 vertices, and we count the numbers of such graphs for which there is another graph with the same generalized permanental polynomial. The present data show that the generalized permanental polynomial is quite efficient for distinguishing graphs. Furthermore, we can write P G ( x , μ ) in the coefficient form ∑ i = 0 n c μ i ( G ) x n − i and obtain the combinatorial expressions for the first five coefficients c μ i ( G ) ( i = 0 , 1 , ⋯ , 4 ) of P G ( x , μ ) .

APA, Harvard, Vancouver, ISO, and other styles

43

Daoud, Mariam, Lynda Tamine, and Mohand Boughanem. "A personalized search using a semantic distance measure in a graph-based ranking model." Journal of Information Science 37, no. 6 (2011): 614–36. http://dx.doi.org/10.1177/0165551511420220.

Full text

Abstract:

The goal of search personalization is to tailor search results to individual users by taking into account their profiles, which include their particular interests and preferences. As these latter are multiple and change over time, personalization becomes effective when the search process takes into account the current user interest. This article presents a search personalization approach that models a semantic user profile and focuses on a personalized document ranking model based on an extended graph-based distance measure. Documents and user profiles are both represented by graphs of concepts issued from predefined web ontology, namely, the Open Directory Project directory (ODP). Personalization is then based on reordering the search results of related queries according to a graph-based document ranking model. This former is based on using a graph-based distance measure combining the minimum common supergraph and the maximum common subgraph between the document and the user profile graphs. We extend this measure in order to take into account a semantic recovery at exact and approximate concept-level matching. Experimental results show the effectiveness of our personalized graph-based ranking model compared with Yahoo and different personalized ranking models performed using classical graph-based measures or vector-space similarity measures.

APA, Harvard, Vancouver, ISO, and other styles

44

YANG, BOTING, RUNTAO ZHANG, YI CAO, and FARONG ZHONG. "Search Numbers in Networks with Special Topologies." Journal of Interconnection Networks 19, no. 01 (2019): 1940004. http://dx.doi.org/10.1142/s0219265919400048.

Full text

Abstract:

In this paper, we consider the problem of finding the minimum number of searchers to sweep networks/graphs with special topological structures. Such a number is called the search number. We first study graphs, which contain only one cycle, and present a linear time algorithm to compute the vertex separation and the optimal layout of such graphs; by a linear-time transformation, we can find the search number of this kind of graphs in linear time. We also investigate graphs, in which every vertex lies on at most one cycle and each cycle contains at most three vertices of degree more than two, and we propose a linear time algorithm to compute their search number and optimal search strategy. We prove explicit formulas for the search number of the graphs obtained from complete k-ary trees by replacing vertices by cycles. We also present some results on approximation algorithms.

APA, Harvard, Vancouver, ISO, and other styles

45

Zeng, Jia-Hui, Jiu-Ming Huang, and Shu-Qiang Yang. "Top-k Keyword Search Over Graphs Based On Backward Search." ITM Web of Conferences 12 (2017): 01014. http://dx.doi.org/10.1051/itmconf/20171201014.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Ramzaev, V. М., I. N. Khaimovich, and I. V. Martynov. "Methods for finding shortest paths on graphs in organizational and economic systems and their implementation." Information Technology and Nanotechnology, no. 2416 (2019): 368–75. http://dx.doi.org/10.18287/1613-0073-2019-2416-368-375.

Full text

Abstract:

The article implements the functions in Postgre SQL DBMS, finding the shortest paths on graphs, using the wave algorithm method, the Dijkstra’s method and the Floyd method. The authors determined models of dependencies of the running time of implementations of the shortest-path search algorithms on graphs on the number of graph vertices experimentally. A comparison of the data obtained as a result of the study was carried out to find the best applications of implementations of the shortest path search algorithms in the Postgre SQL DBMS.

APA, Harvard, Vancouver, ISO, and other styles

47

Gammell, Jonathan D., Timothy D. Barfoot, and Siddhartha S. Srinivasa. "Batch Informed Trees (BIT*): Informed asymptotically optimal anytime search." International Journal of Robotics Research 39, no. 5 (2020): 543–67. http://dx.doi.org/10.1177/0278364919890396.

Full text

Abstract:

Path planning in robotics often requires finding high-quality solutions to continuously valued and/or high-dimensional problems. These problems are challenging and most planning algorithms instead solve simplified approximations. Popular approximations include graphs and random samples, as used by informed graph-based searches and anytime sampling-based planners, respectively. Informed graph-based searches, such as A*, traditionally use heuristics to search a priori graphs in order of potential solution quality. This makes their search efficient, but leaves their performance dependent on the chosen approximation. If the resolution of the chosen approximation is too low, then they may not find a (suitable) solution, but if it is too high, then they may take a prohibitively long time to do so. Anytime sampling-based planners, such as RRT*, traditionally use random sampling to approximate the problem domain incrementally. This allows them to increase resolution until a suitable solution is found, but makes their search dependent on the order of approximation. Arbitrary sequences of random samples approximate the problem domain in every direction simultaneously, but may be prohibitively inefficient at containing a solution. This article unifies and extends these two approaches to develop Batch Informed Trees (BIT*), an informed, anytime sampling-based planner. BIT* solves continuous path planning problems efficiently by using sampling and heuristics to alternately approximate and search the problem domain. Its search is ordered by potential solution quality, as in A*, and its approximation improves indefinitely with additional computational time, as in RRT*. It is shown analytically to be almost-surely asymptotically optimal and experimentally to outperform existing sampling-based planners, especially on high-dimensional planning problems.

APA, Harvard, Vancouver, ISO, and other styles

48

Cai, Shaowei, Jinkun Lin, and Chuan Luo. "Finding A Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess." Journal of Artificial Intelligence Research 59 (July 31, 2017): 463–94. http://dx.doi.org/10.1613/jair.5443.

Full text

Abstract:

The problem of finding a minimum vertex cover (MinVC) in a graph is a well known NP-hard combinatorial optimization problem of great importance in theory and practice. Due to its NP-hardness, there has been much interest in developing heuristic algorithms for finding a small vertex cover in reasonable time. Previously, heuristic algorithms for MinVC have focused on solving graphs of relatively small size, and they are not suitable for solving massive graphs as they usually have high-complexity heuristics. This paper explores techniques for solving MinVC in very large scale real-world graphs, including a construction algorithm, a local search algorithm and a preprocessing algorithm. Both the construction and search algorithms are based on low-complexity heuristics, and we combine them to develop a heuristic algorithm for MinVC called FastVC. Experimental results on a broad range of real-world massive graphs show that, our algorithms are very fast and have better performance than previous heuristic algorithms for MinVC. We also develop a preprocessing algorithm to simplify graphs for MinVC algorithms. By applying the preprocessing algorithm to local search algorithms, we obtain two efficient MinVC solvers called NuMVC2+p and FastVC2+p, which show further improvement on the massive graphs.

APA, Harvard, Vancouver, ISO, and other styles

49

Gerevini, A., A. Saetti, and I. Serina. "Planning Through Stochastic Local Search and Temporal Action Graphs in LPG." Journal of Artificial Intelligence Research 20 (December 1, 2003): 239–90. http://dx.doi.org/10.1613/jair.1183.

Full text

Abstract:

We present some techniques for planning in domains specified with the recent standard language PDDL2.1, supporting 'durative actions' and numerical quantities. These techniques are implemented in LPG, a domain-independent planner that took part in the 3rd International Planning Competition (IPC). LPG is an incremental, any time system producing multi-criteria quality plans. The core of the system is based on a stochastic local search method and on a graph-based representation called 'Temporal Action Graphs' (TA-graphs). This paper focuses on temporal planning, introducing TA-graphs and proposing some techniques to guide the search in LPG using this representation. The experimental results of the 3rd IPC, as well as further results presented in this paper, show that our techniques can be very effective. Often LPG outperforms all other fully-automated planners of the 3rd IPC in terms of speed to derive a solution, or quality of the solutions that can be produced.

APA, Harvard, Vancouver, ISO, and other styles

50

Yue, Jumei, Yongyi Yan, and He Deng. "Matrix Approach to Formulate and Search k-ESS of Graphs Using the STP Theory." Journal of Mathematics 2021 (July 6, 2021): 1–12. http://dx.doi.org/10.1155/2021/7230661.

Full text

Abstract:

In this paper, the structure of graphs in terms of k-externally stable set (k-ESS) is investigated by a matrix method based on a new matrix product, called semitensor product of matrices. By defining an eigenvector and an eigenvalue of the node subset of a graph, three necessary and sufficient conditions of k-ESS, minimum k-ESS, and k-kernels of graphs are proposed in a matrix form, respectively. Using these conditions, the concepts of k-ESS matrix, minimum k-ESS matrix, and k-kernel matrix are introduced. These matrices provide complete information of the corresponding structures of a graph. Further, three algorithms are designed, respectively, to find all these three structures of a graph by conducting a series of matrix operation. Finally, the correctness and effectiveness of the results are checked by studying an example. The proposed method and results may offer a new way to investigate the problems related to graph structures in the field of network systems.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Search in graphs AND'

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