Journal articles: 'Graph algorithmic'

1

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

7

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

8

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

10

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

11

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

13

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

14

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

15

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

16

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

17

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

18

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

19

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

21

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

22

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

23

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

24

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

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, no. 1 (June 1, 2016): 16–40. http://dx.doi.org/10.1515/ausi-2016-0002.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

26

Rai B, Shamantha, and 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.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

27

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

28

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

31

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

32

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

33

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

34

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

35

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

36

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

37

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

38

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

39

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

40

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

41

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

42

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

44

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

45

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

46

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

47

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Graph algorithmic'

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