Relevant bibliographies by topics / Graph problems

Academic literature on the topic 'Graph problems'

Author: Grafiati
Published: 4 June 2021
Last updated: 30 January 2023

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

Select a source type:

Contents

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

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Graph problems"

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 (April 3, 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

Wu, Y., P. Austrin, T. Pitassi, and D. Liu. "Inapproximability of Treewidth and Related Problems." Journal of Artificial Intelligence Research 49 (April 6, 2014): 569–600. http://dx.doi.org/10.1613/jair.4030.

Full text
Abstract:
Graphical models, such as Bayesian Networks and Markov networks play an important role in artificial intelligence and machine learning. Inference is a central problem to be solved on these networks. This, and other problems on these graph models are often known to be hard to solve in general, but tractable on graphs with bounded Treewidth. Therefore, finding or approximating the Treewidth of a graph is a fundamental problem related to inference in graphical models. In this paper, we study the approximability of a number of graph problems: Treewidth and Pathwidth of graphs, Minimum Fill-In, One-Shot Black (and Black-White) pebbling costs of directed acyclic graphs, and a variety of different graph layout problems such as Minimum Cut Linear Arrangement and Interval Graph Completion. We show that, assuming the recently introduced Small Set Expansion Conjecture, all of these problems are NP-hard to approximate to within any constant factor in polynomial time.
APA, Harvard, Vancouver, ISO, and other styles
3

Lynch, Mark A. M. "Creating recreational Hamiltonian cycle problems." Mathematical Gazette 88, no. 512 (July 2004): 215–18. http://dx.doi.org/10.1017/s0025557200174935.

Full text
Abstract:
In this paper graphs that contain unique Hamiltonian cycles are introduced. The graphs are of arbitrary size and dense in the sense that their average vertex degree is greater than half the number of vertices that make up the graph. The graphs can be used to generate challenging puzzles. The problem is particularly challenging when the graph is large and the ‘method’ of solution is unknown to the solver.
APA, Harvard, Vancouver, ISO, and other styles
4

Dhamala, Tanka Nath. "Some Discrete Optimization Problems With Hamming and H-Comparability Graphs." Tribhuvan University Journal 27, no. 1-2 (December 30, 2010): 167–76. http://dx.doi.org/10.3126/tuj.v27i1-2.26400.

Full text
Abstract:
Any H-comparability graph contains a Hamming graph as spanningsubgraph. An acyclic orientation of an H-comparability graph contains an acyclic orientation of the spanning Hamming graph, called sequence graph in the classical open-shop scheduling problem. We formulate different discrete optimization problems on the Hamming graphs and on H-comparability graphs and consider their complexity and relationship. Moreover, we explore the structures of these graphs in the class of irreducible sequences for the open shop problem in this paper.
APA, Harvard, Vancouver, ISO, and other styles
5

Sciriha, Irene. "Joining Forces for Reconstruction Inverse Problems." Symmetry 13, no. 9 (September 13, 2021): 1687. http://dx.doi.org/10.3390/sym13091687.

Full text
Abstract:
A spectral inverse problem concerns the reconstruction of parameters of a parent graph from prescribed spectral data of subgraphs. Also referred to as the P–NP Isomorphism Problem, Reconstruction or Exact Graph Matching, the aim is to seek sets of parameters to determine a graph uniquely. Other related inverse problems, including the Polynomial Reconstruction Problem (PRP), involve the recovery of graph invariants. The PRP seeks to extract the spectrum of a graph from the deck of cards each showing the spectrum of a vertex-deleted subgraph. We show how various algebraic methods join forces to reconstruct a graph or its invariants from a minimal set of restricted eigenvalue-eigenvector information of the parent graph or its subgraphs. We show how functions of the entries of eigenvectors of the adjacency matrix A of a graph can be retrieved from the spectrum of eigenvalues of A. We establish that there are two subclasses of disconnected graphs with each card of the deck showing a common eigenvalue. These could occur as possible counter examples to the positive solution of the PRP.
APA, Harvard, Vancouver, ISO, and other styles
6

Golumbic, M. C., H. Kaplan, and R. Shamir. "Graph Sandwich Problems." Journal of Algorithms 19, no. 3 (November 1995): 449–73. http://dx.doi.org/10.1006/jagm.1995.1047.

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

Makarov, Ilya, Dmitrii Kiselev, Nikita Nikitinsky, and Lovro Subelj. "Survey on graph embeddings and their applications to machine learning problems on graphs." PeerJ Computer Science 7 (February 4, 2021): e357. http://dx.doi.org/10.7717/peerj-cs.357.

Full text
Abstract:
Dealing with relational data always required significant computational resources, domain expertise and task-dependent feature engineering to incorporate structural information into a predictive model. Nowadays, a family of automated graph feature engineering techniques has been proposed in different streams of literature. So-called graph embeddings provide a powerful tool to construct vectorized feature spaces for graphs and their components, such as nodes, edges and subgraphs under preserving inner graph properties. Using the constructed feature spaces, many machine learning problems on graphs can be solved via standard frameworks suitable for vectorized feature representation. Our survey aims to describe the core concepts of graph embeddings and provide several taxonomies for their description. First, we start with the methodological approach and extract three types of graph embedding models based on matrix factorization, random-walks and deep learning approaches. Next, we describe how different types of networks impact the ability of models to incorporate structural and attributed data into a unified embedding. Going further, we perform a thorough evaluation of graph embedding applications to machine learning problems on graphs, among which are node classification, link prediction, clustering, visualization, compression, and a family of the whole graph embedding algorithms suitable for graph classification, similarity and alignment problems. Finally, we overview the existing applications of graph embeddings to computer science domains, formulate open problems and provide experiment results, explaining how different networks properties result in graph embeddings quality in the four classic machine learning problems on graphs, such as node classification, link prediction, clustering and graph visualization. As a result, our survey covers a new rapidly growing field of network feature engineering, presents an in-depth analysis of models based on network types, and overviews a wide range of applications to machine learning problems on graphs.
APA, Harvard, Vancouver, ISO, and other styles
8

Halin, R. "Minimization Problems for Infinite n-Connected Graphs." Combinatorics, Probability and Computing 2, no. 4 (December 1993): 417–36. http://dx.doi.org/10.1017/s096354830000081x.

Full text
Abstract:
A graph G is called n-minimizable if it can be reduced, by deleting a set of its edges, to a minimally n-connected graph. It is shown that, if n-connected graphs G and H differ only by finitely many vertices and edges, then G is n-minimizable if and only if H is n-minimizable (Theorem 4.12). In the main result, conditions are given that a tree decomposition of an n-connected graph G must satisfy in order to guarantee that the n-minimizability of each of the members of this decomposition implies the n-minimizability of the graph G (Theorem 6.5).
APA, Harvard, Vancouver, ISO, and other styles
9

Talebi, A. A., G. Muhiuddin, S. H. Sadati, and Hossein Rashmanlou. "New concepts of domination in fuzzy graph structures with application." Journal of Intelligent & Fuzzy Systems 42, no. 4 (March 4, 2022): 3705–18. http://dx.doi.org/10.3233/jifs-211923.

Full text
Abstract:
Fuzzy graphs have a prominent place in the mathematical modelling of the problems due to the simplicity of representing the relationships between topics. Gradually, with the development of science and in encountering with complex problems and the existence of multiple relationships between variables, the need to consider fuzzy graphs with multiple relationships was felt. With the introduction of the graph structures, there was better flexibility than the graph in dealing with problems. By combining a graph structure with a fuzzy graph, a fuzzy graph structure was introduced that increased the decision-making power of complex problems based on uncertainties. The previous definitions restrictions in fuzzy graphs have made us present new definitions in the fuzzy graph structure. The domination of fuzzy graphs has many applications in other sciences including computer science, intelligent systems, psychology, and medical sciences. Hence, in this paper, first we study the dominating set in a fuzzy graph structure from the perspective of the domination number of its fuzzy relationships. Likewise, we determine the domination in terms of neighborhood, degree, and capacity of vertices with some examples. Finally, applications of domination are introduced in fuzzy graph structure.
APA, Harvard, Vancouver, ISO, and other styles
10

Makhnev, A. A., I. N. Belousov, and D. V. Paduchikh. "Inverse problems of graph theory: Graphs without triangles." Sibirskie Elektronnye Matematicheskie Izvestiya 18, no. 1 (January 21, 2021): 27–42. http://dx.doi.org/10.33048/semi.2021.18.003.

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

Dissertations / Theses on the topic "Graph problems"

1

Pantel, Sarah. "Graph packing problems." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape9/PQDD_0028/MQ51442.pdf.

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

Bessy, Stéphane. "Some problems in graph theory and graphs algorithmic theory." Habilitation à diriger des recherches, Université Montpellier II - Sciences et Techniques du Languedoc, 2012. http://tel.archives-ouvertes.fr/tel-00806716.

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

Nikwigize, Adolphe. "Graph theory : Route problems." Thesis, Linnéuniversitetet, Institutionen för datavetenskap, fysik och matematik, DFM, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-17397.

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

Rackham, Tom. "Problems in graph colouring." Thesis, University of Oxford, 2009. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.526104.

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

Varga, Romy Carleton University Dissertation Mathematics. "Graph connectivity augmentation problems." Ottawa, 1996.

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

Bush, Albert. "Two Problems on Bipartite Graphs." Digital Archive @ GSU, 2009. http://digitalarchive.gsu.edu/math_theses/72.

Full text
Abstract:
Erdos proved the well-known result that every graph has a spanning, bipartite subgraph such that every vertex has degree at least half of its original degree. Bollobas and Scott conjectured that one can get a slightly weaker result if we require the subgraph to be not only spanning and bipartite, but also balanced. We prove this conjecture for graphs of maximum degree 3. The majority of the paper however, will focus on graph tiling. Graph tiling (or sometimes referred to as graph packing) is where, given a graph H, we find a spanning subgraph of some larger graph G that consists entirely of disjoint copies of H. With the Regularity Lemma and the Blow-up Lemma as our main tools, we prove an asymptotic minimum degree condition for an arbitrary bipartite graph G to be tiled by another arbitrary bipartite graph H. This proves a conjecture of Zhao and also implies an asymptotic version of a result of Kuhn and Osthus for bipartite graphs.
APA, Harvard, Vancouver, ISO, and other styles
7

Casselgren, Carl Johan. "On some graph coloring problems." Doctoral thesis, Umeå universitet, Institutionen för matematik och matematisk statistik, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-43389.

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

He, Dayu. "Algorithms for Graph Drawing Problems." Thesis, State University of New York at Buffalo, 2017. http://pqdtopen.proquest.com/#viewpdf?dispub=10284151.

Full text
Abstract:

A graph G is called planar if it can be drawn on the plan such that no two distinct edges intersect each other but at common endpoints. Such drawing is called a plane embedding of G. A plane graph is a graph with a fixed embedding. A straight-line drawing G of a graph G = (V, E) is a drawing where each vertex of V is drawn as a distinct point on the plane and each edge of G is drawn as a line segment connecting two end vertices. In this thesis, we study a set of planar graph drawing problems.

First, we consider the problem of monotone drawing: A path P in a straight line drawing Γ is monotone if there exists a line l such that the orthogonal projections of the vertices of P on l appear along l in the order they appear in P. We call l a monotone line (or monotone direction) of P. G is called a monotone drawing of G if it contains at least one monotone path Puw between every pair of vertices u,w of G. Monotone drawings were recently introduced by Angelini et al. and represent a new visualization paradigm, and is also closely related to several other important graph drawing problems. As in many graph drawing problems, one of the main concerns of this research is to reduce the drawing size, which is the size of the smallest integer grid such that every graph in the graph class can be drawn in such a grid. We present two approaches for the problem of monotone drawings of trees. Our first approach show that every n-vertex tree T admits a monotone drawing on a grid of size O(n1.205) × O( n1.205) grid. Our second approach further reduces the size of drawing to 12n × 12n, which is asymptotically optimal. Both of our two drawings can be constructed in O(n) time.

We also consider monotone drawings of 3-connected plane graphs. We prove that the classical Schnyder drawing of 3-connected plane graphs is a monotone drawing on a f × f grid, which can be constructed in O(n) time.

Second, we consider the problem of orthogonal drawing. An orthogonal drawing of a plane graph G is a planar drawing of G such that each vertex of G is drawn as a point on the plane, and each edge is drawn as a sequence of horizontal and vertical line segments with no crossings. Orthogonal drawing has attracted much attention due to its various applications in circuit schematics, relationship diagrams, data flow diagrams etc. . Rahman et al. gave a necessary and sufficient condition for a plane graph G of maximum degree 3 to have an orthogonal drawing without bends. An orthogonal drawing D(G) is orthogonally convex if all faces of D(G) are orthogonally convex polygons. Chang et al. gave a necessary and sufficient condition (which strengthens the conditions in the previous result) for a plane graph G of maximum degree 3 to have an orthogonal convex drawing without bends. We further strengthen the results such that if G satisfies the same conditions as in previous papers, it not only has an orthogonally convex drawing, but also a stronger star-shaped orthogonal drawing.

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

Lahn, Nathaniel Adam. "A Separator-Based Framework for Graph Matching Problems." Diss., Virginia Tech, 2020. http://hdl.handle.net/10919/98618.

Full text
Abstract:
Given a graph, a matching is a set of vertex-disjoint edges. Graph matchings have been well studied, since they play a fundamental role in algorithmic theory as well as motivate many practical applications. Of particular interest is the problem of finding a maximum cardinality matching of a graph. Also of interest is the weighted variant: the problem of computing a minimum-cost maximum cardinality matching. For an arbitrary graph with m edges and n vertices, there are known, long-standing combinatorial algorithms that compute a maximum cardinality matching in O(m\sqrt{n}) time. For graphs with non-negative integer edge costs at most C, it is known how to compute a minimum-cost maximum cardinality matching in roughly O(m\sqrt{n} log(nC)) time using combinatorial methods. While non-combinatorial methods exist, they are generally impractical and not well understood due to their complexity. As a result, there is great interest in obtaining faster matching algorithms that are purely combinatorial in nature. Improving existing combinatorial algorithms for arbitrary graphs is considered to be a very difficult problem. To make the problem more approachable, it is desirable to make some additional assumptions about the graph. For our work, we make two such assumptions. First, we assume the graph is bipartite. Second, we assume that the graph has a small balanced separator, meaning it is possible to split the graph into two roughly equal-size components by removing a relatively small portion of the graph. Several well-studied classes of graphs have separator-like properties, including planar graphs, minor-free graphs, and geometric graphs. For such graphs, we describe a framework, a general set of techniques for designing efficient algorithms. We demonstrate this framework by applying it to yield polynomial-factor improvements for several open-problems in bipartite matching.
Doctor of Philosophy
Assume we are given a list of objects, and a list of compatible pairs of these objects. A matching consists of a chosen subset of these compatible pairs, where each object participates in at most one chosen pair. For any chosen pair of objects, we say the these two objects are matched. Generally, we seek to maximize the number of compatible matches. A maximum cardinality matching is a matching with the largest possible size. In many cases, there are multiple options for maximizing the number of compatible pairings. While maximizing the size of the matching is often the primary concern, one may also seek to minimize the cost of the matching. This is known as the minimum-cost maximum-cardinality matching problem. These two matching problems have been well studied, since they play a fundamental role in algorithmic theory as well as motivate many practical applications. Our interest is in the design of algorithms for both of these problems that are efficiently scalable, even as the number of objects involved grows very large. To aid in the design of scalable algorithms, we observe that some inputs have good separators, meaning that by removing some subset S of objects, one can divide the remaining objects into two sets V and V', where all pairs of objects between V and V' are incompatible. We design several new algorithms that exploit good separators, and prove that these algorithms scale better than previously existing approaches.
APA, Harvard, Vancouver, ISO, and other styles
10

Edwards, C. S. "Some extremal problems in graph theory." Thesis, University of Reading, 1986. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.373467.

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

Books on the topic "Graph problems"

1

Jensen, Tommy R. Graph coloring problems. New York: Wiley, 1995.

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

Jensen, Tommy R. Graph coloring problems. New York: Wiley, 1995.

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

Jensen, Tommy R., and Bjarne Toft. Graph Coloring Problems. Hoboken, NJ, USA: John Wiley & Sons, Inc., 1994. http://dx.doi.org/10.1002/9781118032497.

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

Goldengorin, Boris, ed. Optimization Problems in Graph Theory. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-94830-0.

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

Bylka, Stanisław. Reconstruction problems for hypergraphs. Warszawa: Institute of Computer Science, [Polish Academy of Science, 1991.

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

Problems in combinatorics and graph theory. New York: Wiley, 1985.

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

1949-, Miller Mirka, ed. Super edge-antimagic graphs: A wealth of problems and some solutions. Boca Raton, Fla: BrownWalker Press, 2008.

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

1913-, Erdős Paul, and Graham Ronald L. 1935-, eds. Erdős on graphs: His legacy of unsolved problems. Wellesley, Mass: AK Peters, 1998.

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

Vasudev, C. Graph theory with applications. New Delhi: New Age International (P) Ltd., Publishers, 2006.

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

V, Melʹnikov O., ed. Exercises in graph theory. Dordrecht: Kluwer Academic Publishers, 1998.

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

Book chapters on the topic "Graph problems"

1

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

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

Smoryński, Craig. "Graph Theory." In Mathematical Problems, 263–339. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-50917-0_5.

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

de Haan, Ronald. "Graph Problems." In Parameterized Complexity in the Polynomial Hierarchy, 261–68. Berlin, Heidelberg: Springer Berlin Heidelberg, 2019. http://dx.doi.org/10.1007/978-3-662-60670-4_13.

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

Raitner, Marcus. "Open Problems Wiki." In Graph Drawing, 508–9. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/978-3-540-31843-9_54.

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

Skiena, Steven S. "Graph Problems: Hard Problems." In The Algorithm Design Manual, 523–61. London: Springer London, 2012. http://dx.doi.org/10.1007/978-1-84800-070-4_16.

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

Köbler, Johannes, Uwe Schöning, and Jacobo Torán. "Decision Problems, Search Problems, and Counting Problems." In The Graph Isomorphism Problem, 11–50. Boston, MA: Birkhäuser Boston, 1993. http://dx.doi.org/10.1007/978-1-4612-0333-9_3.

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

Bollobás, Béla. "Extremal Problems." In Modern Graph Theory, 103–44. New York, NY: Springer New York, 1998. http://dx.doi.org/10.1007/978-1-4612-0619-4_4.

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

Chakradhar, Srimat T., Vishwani D. Agrawal, and Michael L. Bushneil. "Solving Graph Problems." In Neural Models and Algorithms for Digital Testing, 163–74. Boston, MA: Springer US, 1991. http://dx.doi.org/10.1007/978-1-4615-3958-2_13.

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

Díaz, J. "Graph layout problems." In Mathematical Foundations of Computer Science 1992, 14–23. Berlin, Heidelberg: Springer Berlin Heidelberg, 1992. http://dx.doi.org/10.1007/3-540-55808-x_2.

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

Nishizeki, Takao. "Planar Graph Problems." In Computing Supplementum, 53–68. Vienna: Springer Vienna, 1990. http://dx.doi.org/10.1007/978-3-7091-9076-0_3.

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

Conference papers on the topic "Graph problems"

1

Campbell, Matthew I., Sandeep Nair, and Jay Patel. "A Unified Approach to Solving Graph Based Design Problems." In ASME 2007 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. ASMEDC, 2007. http://dx.doi.org/10.1115/detc2007-34523.

Full text
Abstract:
This paper proposes a new perspective of using graph transformation systems as a way of organizing and solving engineering design problems. Using this novel technique the synthesis of optimal solutions in the form of graph topologies for design problems is made possible. Though the concept of graph grammars has existed for several decades in computer science literature, researchers in the field of design have now begun to realize the merit of using them to harness both the knowledge and heuristics of a particular problem domain. This paper examines the fundamental challenges in applying graph transformations in a design context. The paper also presents the first topology optimization method that has been developed specifically for domains representable by a graph grammar schema. This novel approach could also be used in several problems such as network problems (especially in determining the placement of hubs), electric circuit design, neural networks, sheet metal, and product architecture. The abstraction afforded by graphs also enables us to tackle multi-disciplinary problems found throughout engineering design. A few engineering examples are shown in this paper in order to illustrate the power of the approach in automating the design process.
APA, Harvard, Vancouver, ISO, and other styles
2

Zheng, Yujun, and Jinyun Xue. "Problem Reduction Graph Model for Discrete Optimization Problems." In 2010 Third International Joint Conference on Computational Science and Optimization. IEEE, 2010. http://dx.doi.org/10.1109/cso.2010.202.

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

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

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

Hu, Minyang, Hong Chang, Bingpeng Ma, and Shiguang Shan. "Learning Continuous Graph Structure with Bilevel Programming for Graph Neural Networks." In Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. California: International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/424.

Full text
Abstract:
Learning graph structure for graph neural networks (GNNs) is crucial to facilitate the GNN-based downstream learning tasks. It is challenging due to the non-differentiable discrete graph structure and lack of ground-truth. In this paper, we address these problems and propose a novel graph structure learning framework for GNNs. Firstly, we directly model the continuous graph structure with dual-normalization, which implicitly imposes sparse constraint and reduces the influence of noisy edges. Secondly, we formulate the whole training process as a bilevel programming problem, where the inner objective is to optimize the GNNs given learned graphs, while the outer objective is to optimize the graph structure to minimize the generalization error of downstream task. Moreover, for bilevel optimization, we propose an improved Neumann-IFT algorithm to obtain an approximate solution, which is more stable and accurate than existing optimization methods. Besides, it makes the bilevel optimization process memory-efficient and scalable to large graphs. Experiments on node classification and scene graph generation show that our method can outperform related methods, especially with noisy graphs.
APA, Harvard, Vancouver, ISO, and other styles
5

Kraiczy, Sonja, and Ciaran McCreesh. "Solving Graph Homomorphism and Subgraph Isomorphism Problems Faster Through Clique Neighbourhood Constraints." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. California: International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/193.

Full text
Abstract:
Graph homomorphism problems involve finding adjacency-preserving mappings between two given graphs. Although theoretically hard, these problems can often be solved in practice using constraint programming algorithms. We show how techniques from the state-of-the-art in subgraph isomorphism solving can be applied to broader graph homomorphism problems, and introduce a new form of filtering based upon clique-finding. We demonstrate empirically that this filtering is effective for the locally injective graph homomorphism and subgraph isomorphism problems, and gives the first practical constraint programming approach to finding general graph homomorphisms.
APA, Harvard, Vancouver, ISO, and other styles
6

Cavalar, Bruno Pasqualotto. "Ramsey-type problems in orientations of graphs ⇤." In III Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2018. http://dx.doi.org/10.5753/etc.2018.3172.

Full text
Abstract:
The Ramsey number R(H) of a graph H is the minimum number n such that there exists a graph G on n vertices with the property that every two-coloring of its edges contains a monochromatic copy of H. In this work we study a variant of this notion, called the oriented Ramsey problem, for an acyclic oriented graph H~ , in which we require that every orientation G~ of the graph G contains a copy of H~ . We also study the threshold function for this problem in random graphs. Finally, we consider the isometric case, in which we require the copy to be isometric, by which we mean that, for every two vertices x, y 2 V (H~ ) and their respective copies x0, y0 in G~ , the distance between x and y is equal to the distance between x0 and y0.
APA, Harvard, Vancouver, ISO, and other styles
7

Dantas, Simone, and Luerbio Faria. "On Stubborn Graph Sandwich Problems." In 2007 International Multi-Conference on Computing in the Global Information Technology (ICCGI'07). IEEE, 2007. http://dx.doi.org/10.1109/iccgi.2007.41.

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

Feder, Tomas, Pavol Hell, Sulamita Klein, and Rajeev Motwani. "Complexity of graph partition problems." In the thirty-first annual ACM symposium. New York, New York, USA: ACM Press, 1999. http://dx.doi.org/10.1145/301250.301373.

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

Sokolova, A. A., and A. Yu Syshchikov. "THE APPLICATION OF MACHINE LEARNING METHODS TO PROBLEMS ON GRAPHS." In Aerospace instrumentation and operational technologies. Saint Petersburg State University of Aerospace Instrumentation, 2021. http://dx.doi.org/10.31799/978-5-8088-1554-4-2021-2-321-324.

Full text
Abstract:
This article provides an overview of machine learning methods applicable to graph tasks. It also provides a summary of how to represent graphs and a description of the machine learning application to graphs.
APA, Harvard, Vancouver, ISO, and other styles
10

Liu, Yuechang, Hong Qian, and Yunfei Jiang. "Graph-DTP: Graph-Based Algorithm for Solving Disjunctive Temporal Problems." In 14th International Symposium on Temporal Representation and Reasoning (TIME'07). IEEE, 2007. http://dx.doi.org/10.1109/time.2007.50.

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

Reports on the topic "Graph problems"

1

Khanna, S., R. Motwani, and R. H. Wilson. On certificates and lookahead in dynamic graph problems. Office of Scientific and Technical Information (OSTI), May 1995. http://dx.doi.org/10.2172/93769.

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

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

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

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

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

Mniszewski, Susan M., Christian Francisco Negre, and Hayato Montezuma Ushijima-Mwesigwa. Graph Partitioning using the D-Wave for Electronic Structure Problems. Office of Scientific and Technical Information (OSTI), October 2016. http://dx.doi.org/10.2172/1330055.

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

Horan, Victoria, Steve Adachi, and Stanley Bak. A Comparison of Approaches for Solving Hard Graph-Theoretic Problems. Fort Belvoir, VA: Defense Technical Information Center, May 2015. http://dx.doi.org/10.21236/ada623530.

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

Lehoucq, Richard B., Erik Gunnar Boman, Karen D. Devine, Heidi K. Thornquist, and Nicole Lemaster Slattengren. Installing the Anasazi eigensolver package with application to some graph eigenvalue problems. Office of Scientific and Technical Information (OSTI), August 2014. http://dx.doi.org/10.2172/1494630.

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

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

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

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

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

Mikhaleva, E., E. Babikova, G. Bezhashvili, M. Ilina, and I. Samkova. VALUE STREAM PROGRAM. Sverdlovsk Regional Medical College, December 2022. http://dx.doi.org/10.12731/er0618.03122022.

Full text
Abstract:
In order to increase the efficiency of the work of a medical organization, it is necessary to train medical workers, employees of medical organizations, students of educational organizations in the techniques and methods of lean production, followed by the application of the acquired skills directly at the workplace in a medical organization. The purpose of the training under the program is to acquire new competencies necessary to perform professional tasks using lean manufacturing tools - mapping the value stream to ensure maximum operational efficiency of production processes. The program provides for independent work: mapping the value stream of the current, ideal and target states of the process, analysis of the value stream of the current state of the process (problem identification: spaghetti method, pyramid of problems, graph-links, summary table of root causes and contribution of the solution), development of a plan measures to achieve the target state of the process.
APA, Harvard, Vancouver, ISO, and other styles
10

Dror, Moshe, Bezalel Gavish, and Jean Choquette. Directed Steiner Tree Problem on a Graph: Models, Relaxations, and Algorithms. Fort Belvoir, VA: Defense Technical Information Center, August 1988. http://dx.doi.org/10.21236/ada199769.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Graph problems' for particular source types:
Journal articles Dissertations / Theses Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography