Artículos de revistas: "Graph algorithmic"

1

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

2

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

3

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

4

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

5

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

6

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

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

7

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

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

8

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

9

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

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

10

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

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

11

Manacher, Glenn K. "Algorithmic Graph Theory (Alan Gibbons)". SIAM Review 31, n.º 1 (marzo de 1989): 145–47. http://dx.doi.org/10.1137/1031028.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

12

Biswas, Siddhartha. "I-v Fuzzy Shortest Path in a Multigraph". Oriental journal of computer science and technology 10, n.º 2 (25 de marzo de 2017): 364–70. http://dx.doi.org/10.13005/ojcst/10.02.16.

Texto completo

Resumen

In this research paper the author introduces the notion of i-v fuzzy multigraph. The classical Dijkstra’s algorithmic rule to search out the shortest path in graphs isn't applicable to fuzzy graph theory. Consequently the author proposes a brand new algorithmic rule referred to as by IVF-Dijkstra's algorithmic rule with the philosophy of the classical Dijkstra's formula to unravel the SPP in an i-v fuzzy multigraph

Los estilos APA, Harvard, Vancouver, ISO, etc.

13

Kamath, S. S., A. Senthil Thilak y M. Rashmi. "Algorithmic aspects of k-part degree restricted domination in graphs". Discrete Mathematics, Algorithms and Applications 12, n.º 05 (7 de julio de 2020): 2050057. http://dx.doi.org/10.1142/s1793830920500573.

Texto completo

Resumen

The concept of network is predominantly used in several applications of computer communication networks. It is also a fact that the dominating set acts as a virtual backbone in a communication network. These networks are vulnerable to breakdown due to various causes, including traffic congestion. In such an environment, it is necessary to regulate the traffic so that these vulnerabilities could be reasonably controlled. Motivated by this, [Formula: see text]-part degree restricted domination is defined as follows. For a positive integer [Formula: see text], a dominating set [Formula: see text] of a graph [Formula: see text] is said to be a [Formula: see text]-part degree restricted dominating set ([Formula: see text]-DRD set) if for all [Formula: see text], there exists a set [Formula: see text] such that [Formula: see text] and [Formula: see text]. The minimum cardinality of a [Formula: see text]-DRD set of a graph [Formula: see text] is called the [Formula: see text]-part degree restricted domination number of [Formula: see text] and is denoted by [Formula: see text]. In this paper, we present a polynomial time reduction that proves the NP -completeness of the [Formula: see text]-part degree restricted domination problem for bipartite graphs, chordal graphs, undirected path graphs, chordal bipartite graphs, circle graphs, planar graphs and split graphs. We propose a polynomial time algorithm to compute a minimum [Formula: see text]-DRD set of a tree and minimal [Formula: see text]-DRD set of a graph.

Los estilos APA, Harvard, Vancouver, ISO, etc.

14

Doc, Nguyen Van, Nguyen Minh Giam, Nguyen Thi Hoai Nam, Ngo Tu Thanh y Nguyen Thi Huong Giang. "Applying Algorithmic Thinking to Teaching Graphs of Functions For Students Through Geogebra". Journal of Education For Sustainable Innovation 1, n.º 2 (3 de diciembre de 2023): 85–94. http://dx.doi.org/10.56916/jesi.v1i2.554.

Texto completo

Resumen

Algorithmic thinking is a term that is of interest to many educators and teachers. Algorithmic thinking plays an important role not only in problem solving but also in solving real world problems. The article presents some concepts of algorithmic thinking; propose the process of applying algorithmic thinking to teaching function graphs for students through GeoGebra online, helping students to draw all functions in the fastest way. GeoGebra is integrated with algorithms used to graph any function online that students cannot do. GeoGebra is used effectively, interactively and actively supported by many students, students and teachers of Mathematics in the process of graphing functions and graphs in an intuitive and detailed way, thereby developing develop students' thinking.

Los estilos APA, Harvard, Vancouver, ISO, etc.

15

Sharma, Amit y P. Venkata Subba Reddy. "Algorithmic Aspects of Outer-Independent Total Roman Domination in Graphs". International Journal of Foundations of Computer Science 32, n.º 03 (18 de enero de 2021): 331–39. http://dx.doi.org/10.1142/s0129054121500180.

Texto completo

Resumen

For a simple, undirected graph [Formula: see text], a function [Formula: see text] which satisfies the following conditions is called an outer-independent total Roman dominating function (OITRDF) of [Formula: see text] with weight [Formula: see text]. (C1) For all [Formula: see text] with [Formula: see text] there exists a vertex [Formula: see text] such that [Formula: see text] and [Formula: see text], (C2) The induced subgraph with vertex set [Formula: see text] has no isolated vertices and (C3) The induced subgraph with vertex set [Formula: see text] is independent. For a graph [Formula: see text], the smallest possible weight of an OITRDF of [Formula: see text] which is denoted by [Formula: see text], is known as the outer-independent total Roman domination number of [Formula: see text]. The problem of determining [Formula: see text] of a graph [Formula: see text] is called minimum outer-independent total Roman domination problem (MOITRDP). In this article, we show that the problem of deciding if [Formula: see text] has an OITRDF of weight at most [Formula: see text] for bipartite graphs and split graphs, a subclass of chordal graphs is NP-complete. We also show that MOITRDP is linear time solvable for connected threshold graphs and bounded treewidth graphs. Finally, we show that the domination and outer-independent total Roman domination problems are not equivalent in computational complexity aspects.

Los estilos APA, Harvard, Vancouver, ISO, etc.

16

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

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

17

Georgiev, Dobrik, Pietro Barbiero, Dmitry Kazhdan, Petar Veličković y Pietro Lió. "Algorithmic Concept-Based Explainable Reasoning". Proceedings of the AAAI Conference on Artificial Intelligence 36, n.º 6 (28 de junio de 2022): 6685–93. http://dx.doi.org/10.1609/aaai.v36i6.20623.

Texto completo

Resumen

Recent research on graph neural network (GNN) models successfully applied GNNs to classical graph algorithms and combinatorial optimisation problems. This has numerous benefits, such as allowing applications of algorithms when preconditions are not satisfied, or reusing learned models when sufficient training data is not available or can't be generated. Unfortunately, a key hindrance of these approaches is their lack of explainability, since GNNs are black-box models that cannot be interpreted directly. In this work, we address this limitation by applying existing work on concept-based explanations to GNN models. We introduce concept-bottleneck GNNs, which rely on a modification to the GNN readout mechanism. Using three case studies we demonstrate that: (i) our proposed model is capable of accurately learning concepts and extracting propositional formulas based on the learned concepts for each target class; (ii) our concept-based GNN models achieve comparative performance with state-of-the-art models; (iii) we can derive global graph concepts, without explicitly providing any supervision on graph-level concepts.

Los estilos APA, Harvard, Vancouver, ISO, etc.

18

VOIGT, M. "Algorithmic Aspects of Partial List Colourings". Combinatorics, Probability and Computing 9, n.º 4 (julio de 2000): 375–80. http://dx.doi.org/10.1017/s0963548300004259.

Texto completo

Resumen

Let G = (V, E) be a graph with n vertices, chromatic number χ(G) and list chromatic number χ[lscr ](G). Suppose each vertex of V(G) is assigned a list of t colours. Albertson, Grossman and Haas [1] conjectured that at least [formula here] vertices can be coloured properly from these lists.Albertson, Grossman and Haas [1] and Chappell [3] proved partial results concerning this conjecture. This paper presents algorithms that colour at least the number of vertices given in the bounds of Albertson, Grossman and Haas, and Chappell. In particular, it follows that the conjecture is valid for all bipartite graphs and that, for every bipartite graph and every assignment of lists with t colours in each list where 0 [les ] t [les ] χ[lscr ](G), it is possible to colour at least (1 − (1/2)t)n vertices in polynomial time. Thus, if G is bipartite and [Lscr ] is a list assignment with [mid ]L(v)[mid ] [ges ] log2n for all v ∈ V, then G is [Lscr ]-list colourable in polynomial time.

Los estilos APA, Harvard, Vancouver, ISO, etc.

19

Koster, Arie y Vadim Lozin. "DIMAP Workshop on Algorithmic Graph Theory". Electronic Notes in Discrete Mathematics 32 (marzo de 2009): 1. http://dx.doi.org/10.1016/j.endm.2009.02.001.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

20

Pal, Madhumangal y G. P. Bhattacharjee. "A Data Structure on Interval Graphs and Its Applications". Journal of Circuits, Systems and Computers 07, n.º 03 (junio de 1997): 165–75. http://dx.doi.org/10.1142/s0218126697000127.

Texto completo

Resumen

In this papar, a new data structure, interval tree (IT), is introduced for an interval graph. Some important properties of IT are studies from the algorithmic point of view. It has many advantages compared to the data structures which are commonly used to solve the problems on interval graphs. Using the properties of IT, the following problems are solved on interval graphs: (i) shortest distances between any two vertices, and (ii) the diameter of the graph.

Los estilos APA, Harvard, Vancouver, ISO, etc.

21

Fairbairn, David. "Multi-Agent Path-Finding and Algorithmic Graph Theory (Student Abstract)". Proceedings of the International Symposium on Combinatorial Search 16, n.º 1 (2 de julio de 2023): 190–91. http://dx.doi.org/10.1609/socs.v16i1.27308.

Texto completo

Resumen

I specialise in conducting research in Multi-Agent Path- Finding (MAPF) and Algorithmic Graph Theory. Specifically, I investigate the impact of geometric constraints on a given instance of MAPF, as well as the expansion of MAPF to include resource constraints, target assignment path-finding (TAPF), and academic problems that are relevant to industry. In Algorithmic Graph Theory, I extend the capabilities of standard and novel MAPF solvers to temporal graphs, and explore clustering techniques and ideas that utilise Graph Classifications on MAPF domains to reduce the computational complexity of MAPF. Furthermore, I research the implementation and application of massively parallelized computing techniques on MAPF, especially in relation to distance matrix computation and parallelized centralized MAPF. Aside from my PhD research, I have the pleasure to collaborate with researchers at Tharsus Limited, to directly apply my research to novel industrial problems and develop benchmarks that are relevant to both the industry and the research community for Multi-Agent Systems.

Los estilos APA, Harvard, Vancouver, ISO, etc.

22

FANKHAUSER, STEFAN, KASPAR RIESEN, HORST BUNKE y PETER DICKINSON. "SUBOPTIMAL GRAPH ISOMORPHISM USING BIPARTITE MATCHING". International Journal of Pattern Recognition and Artificial Intelligence 26, n.º 06 (septiembre de 2012): 1250013. http://dx.doi.org/10.1142/s0218001412500139.

Texto completo

Resumen

Graphs provide us with a flexible and powerful way to represent objects in various areas of computer science. One of the main drawbacks is, however, that many standard algorithms on graphs have a high computational complexity. The present paper considers the problem of graph isomorphism, i.e. checking two graphs for identity. A novel approach for the efficient computation of graph isomorphism is presented. The proposed algorithm is based on bipartite graph matching by means of an assignment algorithm. The algorithmic framework is suboptimal in the sense of possibly rejecting pairs of graphs without making a decision. As an advantage, however, it offers polynomial runtime. In experiments on diverse graph data sets we demonstrate substantial speedups of our proposed method over several standard procedures for graph isomorphism. Furthermore, although the computational framework for isomorphism is suboptimal, we show that the proposed algorithm rejects only very few pairs of graphs and otherwise returns correct results.

Los estilos APA, Harvard, Vancouver, ISO, etc.

23

Kumar, J. Pavan y P. Venkata Subba Reddy. "Algorithmic Aspects of Some Variants of Domination in Graphs". Analele Universitatii "Ovidius" Constanta - Seria Matematica 28, n.º 3 (1 de diciembre de 2020): 153–70. http://dx.doi.org/10.2478/auom-2020-0039.

Texto completo

Resumen

Abstract A set S ⊆ V is a dominating set in G if for every u ∈ V \ S, there exists v ∈ S such that (u, v) ∈ E, i.e., N[S] = V . A dominating set S is an isolate dominating set (IDS) if the induced subgraph G[S] has at least one isolated vertex. It is known that Isolate Domination Decision problem (IDOM) is NP-complete for bipartite graphs. In this paper, we extend this by showing that the IDOM is NP-complete for split graphs and perfect elimination bipartite graphs, a subclass of bipartite graphs. A set S ⊆ V is an independent set if G[S] has no edge. A set S ⊆ V is a secure dominating set of G if, for each vertex u ∈ V \ S, there exists a vertex v ∈ S such that (u, v) ∈ E and (S \ {v}) ∪ {u} is a dominating set of G. In addition, we initiate the study of a new domination parameter called, independent secure domination. A set S ⊆ V is an independent secure dominating set (InSDS) if S is an independent set and a secure dominating set of G. The minimum size of an InSDS in G is called the independent secure domination number of G and is denoted by γ is (G). Given a graph G and a positive integer k, the InSDM problem is to check whether G has an independent secure dominating set of size at most k. We prove that InSDM is NP-complete for bipartite graphs and linear time solvable for bounded tree-width graphs and threshold graphs, a subclass of split graphs. The MInSDS problem is to find an independent secure dominating set of minimum size, in the input graph. Finally, we show that the MInSDS problem is APX-hard for graphs with maximum degree 5.

Los estilos APA, Harvard, Vancouver, ISO, etc.

24

Vuskovic, Kristina. "Even-hole-free graphs: A survey". Applicable Analysis and Discrete Mathematics 4, n.º 2 (2010): 219–40. http://dx.doi.org/10.2298/aadm100812027v.

Texto completo

Resumen

The class of even-hole-free graphs is structurally quite similar to the class of perfect graphs, which was the key initial motivation for their study. The techniques developed in the study of even-hole-free graphs were generalized to other complex hereditary graph classes, and in the case of perfect graphs led to the famous resolution of the Strong Perfect Graph Conjecture and their polynomial time recognition. The class of even-holefree graphs is also of independent interest due to its relationship to ?-perfect graphs. In this survey we describe all the different structural characterizations of even-hole-free graphs, focusing on their algorithmic consequences.

Los estilos APA, Harvard, Vancouver, ISO, etc.

25

Udaya Kumar Reddy, K. R. "A survey of the all-pairs shortest paths problem and its variants in graphs". Acta Universitatis Sapientiae, Informatica 8, n.º 1 (1 de junio de 2016): 16–40. http://dx.doi.org/10.1515/ausi-2016-0002.

Texto completo

Resumen

Abstract There has been a great deal of interest in the computation of distances and shortest paths problem in graphs which is one of the central, and most studied, problems in (algorithmic) graph theory. In this paper, we survey the exact results of the static version of the all-pairs shortest paths problem and its variants namely, the Wiener index, the average distance, and the minimum average distance spanning tree (MAD tree in short) in graphs (focusing mainly on algorithmic results for such problems). Along the way we also mention some important open issues and further research directions in these areas.

Los estilos APA, Harvard, Vancouver, ISO, etc.

26

Rai B, Shamantha y Shirshu Varma. "An Algorithmic Approach to Wireless Sensor Networks Localization Using Rigid Graphs". Journal of Sensors 2016 (2016): 1–11. http://dx.doi.org/10.1155/2016/3986321.

Texto completo

Resumen

In this work estimating the position coordinates of Wireless Sensor Network nodes using the concept of rigid graphs is carried out in detail. The range based localization approaches use the distance information measured by the RSSI, which is prone to noise, due to effects of path loss, shadowing, and so forth. In this work, both the distance and the bearing information are used for localization using the trilateration technique. Rigid graph theory is employed to analyze the localizability, that is, whether the nodes of the WSN are uniquely localized. The WSN graph is divided into rigid patches by varying appropriately the communication power range of the WSN nodes and then localizing the patches by trilateration. The main advantage of localizing the network using rigid graph approach is that it overcomes the effect of noisy perturbed distance. Our approach gives a better performance compared to robust quads in terms of percentage of localizable nodes and computational complexity.

Los estilos APA, Harvard, Vancouver, ISO, etc.

27

Volchenkov, Dimitri. "Navigability, Walkability, and Perspicacity Associated with Canonical Ensembles of Walks in Finite Connected Undirected Graphs—Toward Information Graph Theory". Information 14, n.º 6 (15 de junio de 2023): 338. http://dx.doi.org/10.3390/info14060338.

Texto completo

Resumen

Canonical ensembles of walks in a finite connected graph assign the properly normalized probability distributions to all nodes, subgraphs, and nodal subsets of the graph at all time and connectivity scales of the diffusion process. The probabilistic description of graphs allows for introducing the quantitative measures of navigability through the graph, walkability of individual paths, and mutual perspicacity of the different modes of the (diffusion) processes. The application of information theory methods to problems about graphs, in contrast to geometric, combinatoric, algorithmic, and algebraic approaches, can be called information graph theory. As it involves evaluating communication efficiency between individual systems’ units at different time and connectivity scales, information graph theory is in demand for a wide range of applications, such as designing network-on-chip architecture and engineering urban morphology within the concept of the smart city.

Los estilos APA, Harvard, Vancouver, ISO, etc.

28

Kozyrev, V. P. y S. V. Yushmanov. "Graph theory (algorithmic, algebraic, and metric problems)". Journal of Soviet Mathematics 39, n.º 1 (octubre de 1987): 2476–508. http://dx.doi.org/10.1007/bf01086177.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

29

Sinha, Deepa y Anshu Sethi. "An Algorithmic Characterization of Splitting Signed Graph". Electronic Notes in Discrete Mathematics 63 (diciembre de 2017): 323–32. http://dx.doi.org/10.1016/j.endm.2017.11.029.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

30

Kumar, H. Naresh y Y. B. Venkatakrishnan. "Algorithmic Aspects of Vertex-edge Domination in Some Graphs". Ars Combinatoria 158, n.º 01 (enero de 2024): 19–26. http://dx.doi.org/10.61091/ars158-03.

Texto completo

Resumen

Let \(G=(V,E)\) be a simple graph. A vertex \(v\in V(G)\) ve-dominates every edge \(uv\) incident to \(v\), as well as every edge adjacent to these incident edges. A set \(D\subseteq V(G)\) is a vertex-edge dominating set if every edge of \(E(G)\) is ve-dominated by a vertex of \(D.\) The MINIMUM VERTEX-EDGE DOMINATION problem is to find a vertex-edge dominating set of minimum cardinality. A linear time algorithm to find the minimum vertex-edge dominating set for proper interval graphs is proposed. The vertex-edge domination problem is proved to be APX-complete for bounded-free graphs and NP-Complete for Chordal bipartite and Undirected Path graphs.

Los estilos APA, Harvard, Vancouver, ISO, etc.

31

Guo, Zhiwei, Hajo Broersma, Ruonan Li y Shenggui Zhang. "Some algorithmic results for finding compatible spanning circuits in edge-colored graphs". Journal of Combinatorial Optimization 40, n.º 4 (4 de septiembre de 2020): 1008–19. http://dx.doi.org/10.1007/s10878-020-00644-7.

Texto completo

Resumen

Abstract A compatible spanning circuit in a (not necessarily properly) edge-colored graph G is a closed trail containing all vertices of G in which any two consecutively traversed edges have distinct colors. Sufficient conditions for the existence of extremal compatible spanning circuits (i.e., compatible Hamilton cycles and Euler tours), and polynomial-time algorithms for finding compatible Euler tours have been considered in previous literature. More recently, sufficient conditions for the existence of more general compatible spanning circuits in specific edge-colored graphs have been established. In this paper, we consider the existence of (more general) compatible spanning circuits from an algorithmic perspective. We first show that determining whether an edge-colored connected graph contains a compatible spanning circuit is an NP-complete problem. Next, we describe two polynomial-time algorithms for finding compatible spanning circuits in edge-colored complete graphs. These results in some sense give partial support to a conjecture on the existence of compatible Hamilton cycles in edge-colored complete graphs due to Bollobás and Erdős from the 1970s.

Los estilos APA, Harvard, Vancouver, ISO, etc.

32

Albert, Reka, Bhaskar DasGupta y Nasim Mobasheri. "Some Perspectives on Network Modeling in Therapeutic Target Prediction". Biomedical Engineering and Computational Biology 5 (enero de 2013): BECB.S10793. http://dx.doi.org/10.4137/becb.s10793.

Texto completo

Resumen

Drug target identification is of significant commercial interest to pharmaceutical companies, and there is a vast amount of research done related to the topic of therapeutic target identification. Interdisciplinary research in this area involves both the biological network community and the graph algorithms community. Key steps of a typical therapeutic target identification problem include synthesizing or inferring the complex network of interactions relevant to the disease, connecting this network to the disease-specific behavior, and predicting which components are key mediators of the behavior. All of these steps involve graph theoretical or graph algorithmic aspects. In this perspective, we provide modelling and algorithmic perspectives for therapeutic target identification and highlight a number of algorithmic advances, which have gotten relatively little attention so far, with the hope of strengthening the ties between these two research communities.

Los estilos APA, Harvard, Vancouver, ISO, etc.

33

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

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

34

Zenil, Hector, Narsis Kiani y Jesper Tegnér. "A Review of Graph and Network Complexity from an Algorithmic Information Perspective". Entropy 20, n.º 8 (25 de julio de 2018): 551. http://dx.doi.org/10.3390/e20080551.

Texto completo

Resumen

Information-theoretic-based measures have been useful in quantifying network complexity. Here we briefly survey and contrast (algorithmic) information-theoretic methods which have been used to characterize graphs and networks. We illustrate the strengths and limitations of Shannon’s entropy, lossless compressibility and algorithmic complexity when used to identify aspects and properties of complex networks. We review the fragility of computable measures on the one hand and the invariant properties of algorithmic measures on the other demonstrating how current approaches to algorithmic complexity are misguided and suffer of similar limitations than traditional statistical approaches such as Shannon entropy. Finally, we review some current definitions of algorithmic complexity which are used in analyzing labelled and unlabelled graphs. This analysis opens up several new opportunities to advance beyond traditional measures.

Los estilos APA, Harvard, Vancouver, ISO, etc.

35

Cynthia, V. Jude Annie. "Algorithmic Approach to Signed Cordiality of Shell Butterfly Networks". Journal of University of Shanghai for Science and Technology 23, n.º 10 (4 de octubre de 2021): 105–14. http://dx.doi.org/10.51201/jusst/21/09705.

Texto completo

Resumen

A shell butterfly graph is defined to be a double shell with exactly two pendant edges at the apex and the right shell with m vertices, the left shell with l vertices. In this paper, we have provided algorithms in order to label the vertices and edges of the graph and have proved that the graph admits signed cordial labeling and signed product cordial labeling.

Los estilos APA, Harvard, Vancouver, ISO, etc.

36

Hu, Fu-Tao, Chang-Xu Zhang y Shu-Cheng Yang. "Algorithmic Complexity and Bounds for Domination Subdivision Numbers of Graphs". Journal of Mathematics 2024 (15 de febrero de 2024): 1–10. http://dx.doi.org/10.1155/2024/3795448.

Texto completo

Resumen

Let G=V,E be a simple graph. A subset D⊆V is a dominating set if every vertex not in D is adjacent to a vertex in D. The domination number of G, denoted by γG, is the smallest cardinality of a dominating set of G. The domination subdivision number sdγG of G is the minimum number of edges that must be subdivided (each edge can be subdivided at most once) in order to increase the domination number. In 2000, Haynes et al. showed that sdγG≤dGv+dGv−1 for any edge uv∈EG with dGu≥2 and dGv≥2 where G is a connected graph with order no less than 3. In this paper, we improve the above bound to sdγG≤dGu+dGv−NGu∩NGv−1, and furthermore, we show the decision problem for determining whether sdγG=1 is NP-hard. Moreover, we show some bounds or exact values for domination subdivision numbers of some graphs.

Los estilos APA, Harvard, Vancouver, ISO, etc.

37

Güvenoglu, Büsra y Belgin Ergenç Bostanoglu. "A qualitative survey on frequent subgraph mining". Open Computer Science 8, n.º 1 (1 de diciembre de 2018): 194–209. http://dx.doi.org/10.1515/comp-2018-0018.

Texto completo

Resumen

AbstractData mining is a popular research area that has been studied by many researchers and focuses on finding unforeseen and important information in large databases. One of the popular data structures used to represent large heterogeneous data in the field of data mining is graphs. So, graph mining is one of the most popular subdivisions of data mining. Subgraphs that are more frequently encountered than the user-defined threshold in a database are called frequent subgraphs. Frequent subgraphs in a database can give important information about this database. Using this information, data can be classified, clustered and indexed. The purpose of this survey is to examine frequent subgraph mining algorithms (i) in terms of frequent subgraph discovery process phases such as candidate generation and frequency calculation, (ii) categorize the algorithms according to their general attributes such as input type, dynamicity of graphs, result type, algorithmic approach they are based on, algorithmic design and graph representation as well as (iii) to discuss the performance of algorithms in comparison to each other and the challenges faced by the algorithms recently.

Los estilos APA, Harvard, Vancouver, ISO, etc.

38

Pramanik, Tarasankar, Sukumar Mondal y Madhumangal Pal. "Minimum 2-Tuple Dominating Set of an Interval Graph". International Journal of Combinatorics 2011 (26 de diciembre de 2011): 1–14. http://dx.doi.org/10.1155/2011/389369.

Texto completo

Resumen

The k-tuple domination problem, for a fixed positive integer k, is to find a minimum size vertex subset such that every vertex in the graph is dominated by at least k vertices in this set. The case when k=2 is called 2-tuple domination problem or double domination problem. In this paper, the 2-tuple domination problem is studied on interval graphs from an algorithmic point of view, which takes O(n2) time, n is the total number of vertices of the interval graph.

Los estilos APA, Harvard, Vancouver, ISO, etc.

39

Medová, Páleníková, Rybanský y Naštická. "Undergraduate Students’ Solutions of Modeling Problems in Algorithmic Graph Theory". Mathematics 7, n.º 7 (26 de junio de 2019): 572. http://dx.doi.org/10.3390/math7070572.

Texto completo

Resumen

Graphs can be considered as useful mathematical models. Graph algorithms are a common part of undergraduate courses in discrete mathematics. Even though they have been successfully implemented in secondary curricula, little research has been dedicated to the analysis of students’ work. Within a discrete mathematics course for university students, several graph algorithms were introduced via their applications. At the end of the course, the students took a test focused, inter alia, on applications of the algorithms. The mistakes that occurred in 127 students’ solutions of three problems (the Chinese postman problem, the shortest path problem, and the minimum spanning tree problem) were categorized and compared. Surprisingly, no mistakes were identified in the mathematization of situations or in the interpretation of results with respect to the wording of the problem. The categories of errors varied regardless of the problem types. Hierarchical cluster analysis grouped together the students’ solutions for the Chinese postman problem and the minimum spanning tree problem. By means of nonparametric item response theory analysis, the Chinese postman problem was identified as the most problematic for students. Possible sources of this difficulty are discussed in more detail herein.

Los estilos APA, Harvard, Vancouver, ISO, etc.

40

Li, Mingxuan y Michael L. Littman. "Towards Sample Efficient Agents through Algorithmic Alignment (Student Abstract)". Proceedings of the AAAI Conference on Artificial Intelligence 35, n.º 18 (18 de mayo de 2021): 15827–28. http://dx.doi.org/10.1609/aaai.v35i18.17910.

Texto completo

Resumen

In this work, we propose and explore Deep Graph Value Network (DeepGV) as a promising method to work around sample complexity in deep reinforcement-learning agents using a message-passing mechanism. The main idea is that the agent should be guided by structured non-neural-network algorithms like dynamic programming. According to recent advances in algorithmic alignment, neural networks with structured computation procedures can be trained efficiently. We demonstrate the potential of graph neural network in supporting sample efficient learning by showing that Deep Graph Value Network can outperform unstructured baselines by a large margin in solving Markov Decision Process (MDP). We believe this would open up a new avenue for structured agents design. See https://github.com/drmeerkat/Deep-Graph-Value-Network for the code.

Los estilos APA, Harvard, Vancouver, ISO, etc.

41

PANDA, B. S. y S. PAUL. "CONNECTED LIAR'S DOMINATION IN GRAPHS: COMPLEXITY AND ALGORITHMS". Discrete Mathematics, Algorithms and Applications 05, n.º 04 (diciembre de 2013): 1350024. http://dx.doi.org/10.1142/s1793830913500249.

Texto completo

Resumen

A subset L ⊆ V of a graph G = (V, E) is called a connected liar's dominating set of G if (i) for all v ∈ V, |NG[v] ∩ L| ≥ 2, (ii) for every pair u, v ∈ V of distinct vertices, |(NG[u]∪NG[v])∩L| ≥ 3, and (iii) the induced subgraph of G on L is connected. In this paper, we initiate the algorithmic study of minimum connected liar's domination problem by showing that the corresponding decision version of the problem is NP-complete for general graph. Next we study this problem in subclasses of chordal graphs where we strengthen the NP-completeness of this problem for undirected path graph and prove that this problem is linearly solvable for block graphs. Finally, we propose an approximation algorithm for minimum connected liar's domination problem and investigate its hardness of approximation in general graphs.

Los estilos APA, Harvard, Vancouver, ISO, etc.

42

Khan, Gitosree, Sabnam Sengupta y Ananya Kanjilal. "Representation and Analysis of Object Oriented Graph (OOG): A Graph Algorithmic Approach". International Journal of Computer Applications 55, n.º 4 (20 de octubre de 2012): 30–37. http://dx.doi.org/10.5120/8745-2626.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

43

Pavlogiannis, Andreas. "CFL/Dyck Reachability". ACM SIGLOG News 9, n.º 4 (octubre de 2022): 5–25. http://dx.doi.org/10.1145/3583660.3583664.

Texto completo

Resumen

CFL/Dyck reachability is a simple graph-theoretic problem: given a CFL/Dyck language L over an alphabet Σ, a graph G = ( V , E ) of Σ-labeled edges, and two distinguished nodes s , t ∈ V , does there exist a path from s to t that spells out a word in L ? This simple notion of language-based graph reachability serves as the algorithmic formulation of a large number of problems in diverse domains, such as graph databases and program static analysis. This paper takes an algorithmic perspective on CFL/Dyck reachability, and overviews several recent advances concerning the decidability and complexity of the problem and some its close variants, as realized in the areas of automata theory and program verification.

Los estilos APA, Harvard, Vancouver, ISO, etc.

44

VAN DEN HEUVEL, JAN. "Algorithmic Aspects of a Chip-Firing Game". Combinatorics, Probability and Computing 10, n.º 6 (noviembre de 2001): 505–29. http://dx.doi.org/10.1017/s0963548301004886.

Texto completo

Resumen

Algorithmic aspects of a chip-firing game on a graph introduced by Biggs are studied. This variant of the chip-firing game, called the dollar game, has the properties that every starting configuration leads to a so-called critical configuration. The set of critical configurations has many interesting properties. In this paper it is proved that the number of steps needed to reach a critical configuration is polynomial in the number of edges of the graph and the number of chips in the starting configuration, but not necessarily in the size of the input. An alternative algorithm is also described and analysed.

Los estilos APA, Harvard, Vancouver, ISO, etc.

45

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

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

46

Drewniak, Józef, Paulina Garlicka, Jerzy Kopeć y Stanisław Zawiślak. "Dynamics of Linkage Mechanism Solved by Means of Contour Graphs and Bond Graphs". Solid State Phenomena 251 (julio de 2016): 224–29. http://dx.doi.org/10.4028/www.scientific.net/ssp.251.224.

Texto completo

Resumen

The dynamical analysis of a linkage mechanism is described in the paper. The contour graph method was utilized. The method allows for assigning a contour graph to a particular mechanism. In next step analysis is performed in algorithmic manner distinguishing the contours and generating kinematical and dynamical equations based upon theses contours. Decomposition of the system is utilized, therefore more simple subsystems are analyzed. Aggregated solution is compatible with all other classical methods however the approach is algorithmic and effective.

Los estilos APA, Harvard, Vancouver, ISO, etc.

47

Amudha, P., J. Jayapriya y J. Gowri. "An Algorithmic Approach for Encryption using Graph Labeling". Journal of Physics: Conference Series 1770, n.º 1 (1 de marzo de 2021): 012072. http://dx.doi.org/10.1088/1742-6596/1770/1/012072.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

48

Kalita, Pranab. "A Graph Theoretical Algorithmic Approach for DNA Sequencing". IOSR Journal of Mathematics 5, n.º 1 (2013): 40–46. http://dx.doi.org/10.9790/5728-0514046.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

49

Baidari, Ishwar, H. B Walikar y Shridevi Shinde. "Algorithmic Approach to Star Partition of the Graph". International Journal of Computer Applications 58, n.º 1 (15 de noviembre de 2012): 41–43. http://dx.doi.org/10.5120/9250-3416.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

50

Gerber, Michael U. y Daniel Kobler. "Algorithmic approach to the satisfactory graph partitioning problem". European Journal of Operational Research 125, n.º 2 (septiembre de 2000): 283–91. http://dx.doi.org/10.1016/s0377-2217(99)00459-2.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Artículos de revistas sobre el tema "Graph algorithmic"

Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros