Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Graphe de communication.
Статті в журналах з теми "Graphe de communication"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся з топ-50 статей у журналах для дослідження на тему "Graphe de communication".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Переглядайте статті в журналах для різних дисциплін та оформлюйте правильно вашу бібліографію.
1
Hilton, N. Zoe, Elke Ham, Kevin L. Nunes, Nicole C. Rodrigues, Cairina Frank, and Michael C. Seto. "Using Graphs to Improve Violence Risk Communication." Criminal Justice and Behavior 44, no. 5 (September 22, 2016): 678–94. http://dx.doi.org/10.1177/0093854816668916.
Повний текст джерелаАнотація:
We examined the use of graphs as an aid to communicating statistical risk among forensic clinicians. We first tested four graphs previously used or recommended for forensic risk assessment among 442 undergraduate students who made security recommendations about two offenders whose risk differed by one actuarial category of risk for violent recidivism (Study 1). Effective decision making was defined as actuarially higher risk offenders being assigned to greater security than lower risk offenders. The graph resulting in the largest distinction among less numerate students was a probability bar graph. We then tested this graph among 54 forensic clinicians (Study 2). The graph had no overall effect. Among more experienced staff, however, decisions were insensitive to actuarial risk in the absence of the graph and in the desirable direction with the addition of the graph. Further research into the benefit of graphs in violence risk communication appears viable.
2
SHOUBRIDGE, PETER, MIRO KRAETZL, WAL WALLIS, and HORST BUNKE. "DETECTION OF ABNORMAL CHANGE IN A TIME SERIES OF GRAPHS." Journal of Interconnection Networks 03, no. 01n02 (March 2002): 85–101. http://dx.doi.org/10.1142/s0219265902000562.
Повний текст джерелаАнотація:
In the management of large enterprise communication networks, it becomes difficult to detect and identify causes of abnormal change in traffic distributions when the underlying logical topology is dynamic. This paper describes a novel approach to abnormal network change detection by representing periodic observations of logical communications within a network as a time series of graphs. A number of graph distance measures are proposed to assess the difference between successive graphs and identify abnormal behaviour. Localisation techniques have also been described to show where in the network most change occurred.
3
Kusper, Gábor, and Csaba Biró. "Convert a Strongly Connected Directed Graph to a Black-and-White 3-SAT Problem by the Balatonboglár Model." Algorithms 13, no. 12 (December 3, 2020): 321. http://dx.doi.org/10.3390/a13120321.
Повний текст джерелаАнотація:
In a previous paper we defined the black and white SAT problem which has exactly two solutions, where each variable is either true or false. We showed that black and white 2-SAT problems represent strongly connected directed graphs. We presented also the strong model of communication graphs. In this work we introduce two new models, the weak model, and the Balatonboglár model of communication graphs. A communication graph is a directed graph, where no self loops are allowed. In this work we show that the weak model of a strongly connected communication graph is a black and white SAT problem. We prove a powerful theorem, the so called transitions theorem. This theorem states that for any model which is between the strong and the weak model, we have that this model represents strongly connected communication graphs as black and white SAT problems. We show that the Balatonboglár model is between the strong and the weak model, and it generates 3-SAT problems, so the Balatonboglár model represents strongly connected communication graphs as black and white 3-SAT problems. Our motivation to study these models is the following: The strong model generates a 2-SAT problem from the input directed graph, so it does not give us a deep insight how to convert a general SAT problem into a directed graph. The weak model generates huge models, because it represents all cycles, even non-simple cycles, of the input directed graph. We need something between them to gain more experience. From the Balatonboglár model we learned that it is enough to have a subset of a clause, which represents a cycle in the weak model, to make the Balatonboglár model more compact. We still do not know how to represent a SAT problem as a directed graph, but this work gives a strong link between two prominent fields of formal methods: the SAT problem and directed graphs.
4
LI, YINKUI, ZONGTIAN WEI, XIAOKUI YUE, and ERQIANG LIU. "TENACITY OF TOTAL GRAPHS." International Journal of Foundations of Computer Science 25, no. 05 (August 2014): 553–62. http://dx.doi.org/10.1142/s012905411450021x.
Повний текст джерелаАнотація:
Communication networks must be constructed to be as stable as possible, not only with the respect to the initial disruption, but also with respect to the possible reconstruction. Many graph theoretical parameters have been used to describe the stability of communication networks. Tenacity is a reasonable one, which shows not only the difficulty to break down the network but also the damage that has been caused. Total graphs are the largest graphs formed by the adjacent relations of elements of a graph. Thus, total graphs are highly recommended for the design of interconnection networks. In this paper, we determine the tenacity of the total graph of a path, cycle and complete bipartite graph, and thus give a lower bound of the tenacity for the total graph of a graph.
5
Alanazi, A. M., G. Muhiuddin, A. R. Kannan, and V. Govindan. "New Perspectives on Classical Meanness of Some Ladder Graphs." Journal of Mathematics 2021 (June 30, 2021): 1–14. http://dx.doi.org/10.1155/2021/9926350.
Повний текст джерелаАнотація:
In this study, we investigate a new kind of mean labeling of graph. The ladder graph plays an important role in the area of communication networks, coding theory, and transportation engineering. Also, we found interesting new results corresponding to classical mean labeling for some ladder-related graphs and corona of ladder graphs with suitable examples.
6
Eshaghian, Mary Mehrnoosh. "MAPPING ARBITRARY HETEROGENEOUS TASK GRAPHS ONTO ARBITRARY HETEROGENEOUS SYSTEM GRAPH." International Journal of Foundations of Computer Science 12, no. 05 (October 2001): 599–628. http://dx.doi.org/10.1142/s0129054101000680.
Повний текст джерелаАнотація:
In this paper, a generic technique for mapping arbitrary heterogeneous task graphs onto arbitrary heterogeneous system graphs is presented. The heterogeneous task and system graphs studied in this paper have nonuniform computation and communication weights associated with the nodes and the edges. Two clustering algorithms have been proposed that can be used to obtain a multilayer clustered graph called a Spec graph from a given task graph and a multilayer clustered graph called a Rep graph from a given system graph. We present a mapping algorithm that produces a suboptimal matching of a given Spec graph containing M task modules onto a Rep graph of N processors, in O(M2) time, where N ≤ M. Our experimental results indicate that our mapping algorithm is the fastest one and generates results that are better than, or similar to, those of other leading techniques, some of which work only for restricted task or system graphs.
7
Manjusha, O. T. "Set Domination in Fuzzy Graphs Using Strong Arcs." Pan-American Journal of Mathematics 1 (August 3, 2022): 9. http://dx.doi.org/10.28919/cpr-pajm/1-9.
Повний текст джерелаАнотація:
Set domination in fuzzy graphs is very useful for solving traffic problems during communication in computer networks and travelling networks. In this article, the concept of set domination in fuzzy graphs using strong arcs is introduced. The strong set domination number of complete fuzzy graph and complete bipartite fuzzy graph is determined. It is obtained the properties of the new parameter and related it to some other known domination parameters of fuzzy graphs. An upper bound for the strong set domination number of fuzzy graphs is also obtained.
8
Yang, Chao, Bing Yao, Hong Yu Wang, Xiang'en Chen, and Si Hua Yang. "Graph Colorings Applied in Scale-Free Networks." Advanced Materials Research 760-762 (September 2013): 2199–204. http://dx.doi.org/10.4028/www.scientific.net/amr.760-762.2199.
Повний текст джерелаАнотація:
Building up graph models to simulate scale-free networks is an important method since graphs have been used in researching scale-free networks and communication networks, such as graph colorings can be used for distinguishing objects of communication and information networks. In this paper we determine the avdtc chromatic numbers of some models related with researching networks.
9
RANAWAKE, U. A., P. M. LENDERS, and S. M. GOODNICK. "ON LOWER BOUNDS FOR THE COMMUNICATION VOLUME IN DISTRIBUTED SYSTEMS." Parallel Processing Letters 01, no. 02 (December 1991): 125–33. http://dx.doi.org/10.1142/s0129626491000070.
Повний текст джерелаАнотація:
In this paper we derive a lower bound for the total communication volume when mapping arbitrary task graphs onto a distributed processor system. For a K processor system this lower bound can be computed with only the K (possibly) largest eigen values of the adjacency matrix of the task graph and the eigen values of the adjacency matrix of the processor graph. We also derive the eigen values of the adjacency matrix of the processor graph for a hypercube multiprocessor and illustrate the concept with a simple example for the two processor case.
10
Manghi, Paolo, Claudio Atzori, Michele De Bonis, and Alessia Bardi. "Entity deduplication in big data graphs for scholarly communication." Data Technologies and Applications 54, no. 4 (June 26, 2020): 409–35. http://dx.doi.org/10.1108/dta-09-2019-0163.
Повний текст джерелаАнотація:
PurposeSeveral online services offer functionalities to access information from “big research graphs” (e.g. Google Scholar, OpenAIRE, Microsoft Academic Graph), which correlate scholarly/scientific communication entities such as publications, authors, datasets, organizations, projects, funders, etc. Depending on the target users, access can vary from search and browse content to the consumption of statistics for monitoring and provision of feedback. Such graphs are populated over time as aggregations of multiple sources and therefore suffer from major entity-duplication problems. Although deduplication of graphs is a known and actual problem, existing solutions are dedicated to specific scenarios, operate on flat collections, local topology-drive challenges and cannot therefore be re-used in other contexts.Design/methodology/approachThis work presents GDup, an integrated, scalable, general-purpose system that can be customized to address deduplication over arbitrary large information graphs. The paper presents its high-level architecture, its implementation as a service used within the OpenAIRE infrastructure system and reports numbers of real-case experiments.FindingsGDup provides the functionalities required to deliver a fully-fledged entity deduplication workflow over a generic input graph. The system offers out-of-the-box Ground Truth management, acquisition of feedback from data curators and algorithms for identifying and merging duplicates, to obtain an output disambiguated graph.Originality/valueTo our knowledge GDup is the only system in the literature that offers an integrated and general-purpose solution for the deduplication graphs, while targeting big data scalability issues. GDup is today one of the key modules of the OpenAIRE infrastructure production system, which monitors Open Science trends on behalf of the European Commission, National funders and institutions.
11
Wang, Hong Yu, Bing Yao, Chao Yang, Si Hua Yang, Xiang En Chen, Ming Yao, and Zhen Xue Zhao. "Edge-Magic Total Labellings of some Network Models." Applied Mechanics and Materials 347-350 (August 2013): 2752–57. http://dx.doi.org/10.4028/www.scientific.net/amm.347-350.2752.
Повний текст джерелаАнотація:
It has been known that edge-symmetric graphs can be used as models of some scale-free networks, such as hierarchial networks and self-similar networks, such as graph colorings can be used for distinguishing objects of communication and informa-tion networks. We study the edge-magic property of edge-symmetric graphs, and construct graphs having edge-magic total labellings from smaller graphs.
12
Turaci, Tufan, and Hüseyin Aksan. "The Vulnerability of Some Networks including Cycles via Domination Parameters." Journal of Optimization 2016 (2016): 1–8. http://dx.doi.org/10.1155/2016/4705493.
Повний текст джерелаАнотація:
LetG=(V(G),E(G))be an undirected simple connected graph. A network is usually represented by an undirected simple graph where vertices represent processors and edges represent links between processors. Finding the vulnerability values of communication networks modeled by graphs is important for network designers. The vulnerability value of a communication network shows the resistance of the network after the disruption of some centers or connection lines until a communication breakdown. The domination number and its variations are the most important vulnerability parameters for network vulnerability. Some variations of domination numbers are the 2-domination number, the bondage number, the reinforcement number, the average lower domination number, the average lower 2-domination number, and so forth. In this paper, we study the vulnerability of cycles and related graphs, namely, fans,k-pyramids, andn-gon books, via domination parameters. Then, exact solutions of the domination parameters are obtained for the above-mentioned graphs.
13
MATHEW, SUNIL. "ON CYCLE CONNECTIVITY OF GRAPHS." Journal of Interconnection Networks 13, no. 01n02 (March 2012): 1250005. http://dx.doi.org/10.1142/s0219265912500053.
Повний текст джерелаАнотація:
In this article, the concept of cycle connectivity of a weighted graph is discussed. Cycle connectivity of partial trees, cycles and precisely weighted graphs are obtained. Also the concepts of cyclic cutnode and cyclic bridge in weighted graphs are introduced and a condition for a precisely weighted graph to possess a cyclic cutnode is obtained.
14
Yang, Hong, Muhammad Siddiqui, Muhammad Ibrahim, Sarfraz Ahmad, and Ali Ahmad. "Computing The Irregularity Strength of Planar Graphs." Mathematics 6, no. 9 (August 30, 2018): 150. http://dx.doi.org/10.3390/math6090150.
Повний текст джерелаАнотація:
The field of graph theory plays a vital role in various fields. One of the important areas in graph theory is graph labeling used in many applications such as coding theory, X-ray crystallography, radar, astronomy, circuit design, communication network addressing, and data base management. In this paper, we discuss the totally irregular total k labeling of three planar graphs. If such labeling exists for minimum value of a positive integer k, then this labeling is called totally irregular total k labeling and k is known as the total irregularity strength of a graph G. More preciously, we determine the exact value of the total irregularity strength of three planar graphs.
15
Weaver, Nik. "Quantum Graphs as Quantum Relations." Journal of Geometric Analysis 31, no. 9 (January 13, 2021): 9090–112. http://dx.doi.org/10.1007/s12220-020-00578-w.
Повний текст джерелаАнотація:
AbstractThe “noncommutative graphs” which arise in quantum error correction are a special case of the quantum relations introduced in Weaver (Quantum relations. Mem Am Math Soc 215(v–vi):81–140, 2012). We use this perspective to interpret the Knill–Laflamme error-correction conditions (Knill and Laflamme in Theory of quantum error-correcting codes. Phys Rev A 55:900-911, 1997) in terms of graph-theoretic independence, to give intrinsic characterizations of Stahlke’s noncommutative graph homomorphisms (Stahlke in Quantum zero-error source-channel coding and non-commutative graph theory. IEEE Trans Inf Theory 62:554–577, 2016) and Duan, Severini, and Winter’s noncommutative bipartite graphs (Duan et al., op. cit. in Zero-error communication via quantum channels, noncommutative graphs, and a quantum Lovász number. IEEE Trans Inf Theory 59:1164–1174, 2013), and to realize the noncommutative confusability graph associated to a quantum channel (Duan et al., op. cit. in Zero-error communication via quantum channels, noncommutative graphs, and a quantum Lovász number. IEEE Trans Inf Theory 59:1164–1174, 2013) as the pullback of a diagonal relation. Our framework includes as special cases not only purely classical and purely quantum information theory, but also the “mixed” setting which arises in quantum systems obeying superselection rules. Thus we are able to define noncommutative confusability graphs, give error correction conditions, and so on, for such systems. This could have practical value, as superselection constraints on information encoding can be physically realistic.
16
SHERMAN, DAVID, MING TSAI, CHENG-KUAN LIN, LÁSZLÓ LIPTÁK, EDDIE CHENG, JIMMY J. M. TAN, and LIH-HSING HSU. "4-ORDERED HAMILTONICITY FOR SOME CHORDAL RING GRAPHS." Journal of Interconnection Networks 11, no. 03n04 (September 2010): 157–74. http://dx.doi.org/10.1142/s0219265910002787.
Повний текст джерелаАнотація:
A graph G is k-ordered if for any sequence of k distinct vertices of G, there exists a cycle in G containing these k vertices in the specified order. It is k-ordered Hamiltonian if, in addition, the required cycle is Hamiltonian. The question of the existence of an infinite class of 3-regular 4-ordered Hamiltonian graphs was posed in 1997 by Ng and Schultz.13At the time, the only known examples were K4and K3,3. Some progress was made in 2008 by Mészáros,12when the Peterson graph was found to be 4-ordered and the Heawood graph was proved to be 4-ordered Hamiltonian; moreover, an infinite class of 3-regular 4-ordered graphs was found. In 2010 a subclass of generalized Petersen graphs was shown to be 4-ordered by Hsu et al.,10with an infinite subset of this subclass being 4-ordered Hamiltonian, thus answering the open question. In this paper we find another infinite class of 3-regular 4-ordered Hamiltonian graphs, part of a subclass of the chordal ring graphs. In addition, we classify precisely which of these graphs are 4-ordered Hamiltonian.
17
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.
Повний текст джерелаАнотація:
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.
18
Zhu, Chun Jiang, Tan Zhu, Kam-Yiu Lam, Song Han, and Jinbo Bi. "Communication-Optimal Distributed Dynamic Graph Clustering." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 5957–64. http://dx.doi.org/10.1609/aaai.v33i01.33015957.
Повний текст джерелаАнотація:
We consider the problem of clustering graph nodes over large-scale dynamic graphs, such as citation networks, images and web networks, when graph updates such as node/edge insertions/deletions are observed distributively. We propose communication-efficient algorithms for two well-established communication models namely the message passing and the blackboard models. Given a graph with n nodes that is observed at s remote sites over time [1,t], the two proposed algorithms have communication costs Õ(ns) and Õ(n + s) (Õ hides a polylogarithmic factor), almost matching their lower bounds, Ω(ns) and Ω(n + s), respectively, in the message passing and the blackboard models. More importantly, we prove that at each time point in [1,t] our algorithms generate clustering quality nearly as good as that of centralizing all updates up to that time and then applying a standard centralized clustering algorithm. We conducted extensive experiments on both synthetic and real-life datasets which confirmed the communication efficiency of our approach over baseline algorithms while achieving comparable clustering results.
19
Finta, Lucian, and Zhen Liu. "Complexity of Task Graph Scheduling with Fixed Communication Capacity." International Journal of Foundations of Computer Science 08, no. 01 (March 1997): 43–66. http://dx.doi.org/10.1142/s0129054197000045.
Повний текст джерелаАнотація:
Consider a scheduling problem of parallel computations in multiprocessor systems. Let a parallel program be modeled by a task graph, where vertices represent tasks and arcs the communications between tasks. An interprocessor communication time incurs when two tasks assigned to two different processors have to communicate. Such a scheduling problem has recently been studied in the literature, mostly for the case where interprocessor communication times are fully determined. In this paper, we consider the scheduling problem with communication resource constraints. More specifically, we consider the case where all interprocessor communications take place on a network of bounded capacity. We consider two variants of the problem: communications with independent-data semantics and common-data semantics. We show that even for very specific subproblems, viz. scheduling of general graphs on two processors and scheduling of binary trees on an infinite number of processors, the minimization of the makespan of parallel programs in such a multiprocessor system is strongly [Formula: see text]-hard. We first establish the results for the case of capacity 1, referred to as the single-bus system. We then extend the results to the more general case of fixed communication capacities. As a consequence, the general scheduling problem of parallel programs with communication resource constraints is strongly [Formula: see text]-hard. These results are to be contrasted with the corresponding scheduling problems without contraint on the communication capacity, where the two-processor case has unknown time complexity and the infinite-processor case is polynomial. Our results are also extended to the case of broadcasting communications, and can be applied to multiprocessor systems with shared memory.
20
Elahi, Kashif, Ali Ahmad, and Roslan Hasni. "Construction Algorithm for Zero Divisor Graphs of Finite Commutative Rings and Their Vertex-Based Eccentric Topological Indices." Mathematics 6, no. 12 (December 4, 2018): 301. http://dx.doi.org/10.3390/math6120301.
Повний текст джерелаАнотація:
Chemical graph theory is a branch of mathematical chemistry which deals with the non-trivial applications of graph theory to solve molecular problems. Graphs containing finite commutative rings also have wide applications in robotics, information and communication theory, elliptic curve cryptography, physics, and statistics. In this paper we discuss eccentric topological indices of zero divisor graphs of commutative rings Z p 1 p 2 × Z q , where p 1 , p 2 , and q are primes. To enhance the importance of these indices a construction algorithm is also devised for zero divisor graphs of commutative rings Z p 1 p 2 × Z q .
21
Zhang, Xianhang, Hanchen Wang, Jianke Yu, Chen Chen, Xiaoyang Wang, and Wenjie Zhang. "Polarity-based graph neural network for sign prediction in signed bipartite graphs." World Wide Web 25, no. 2 (February 16, 2022): 471–87. http://dx.doi.org/10.1007/s11280-022-01015-4.
Повний текст джерелаАнотація:
AbstractAs a fundamental data structure, graphs are ubiquitous in various applications. Among all types of graphs, signed bipartite graphs contain complex structures with positive and negative links as well as bipartite settings, on which conventional graph analysis algorithms are no longer applicable. Previous works mainly focus on unipartite signed graphs or unsigned bipartite graphs separately. Several models are proposed for applications on the signed bipartite graphs by utilizing the heuristic structural information. However, these methods have limited capability to fully capture the information hidden in such graphs. In this paper, we propose the first graph neural network on signed bipartite graphs, namely Polarity-based Graph Convolutional Network (PbGCN), for sign prediction task with the help of balance theory. We introduce the novel polarity attribute to signed bipartite graphs, based on which we construct one-mode projection graphs to allow the GNNs to aggregate information between the same type nodes. Extensive experiments on five datasets demonstrate the effectiveness of our proposed techniques.
22
Erlebach, Thomas, and Jakob T. Spooner. "Exploration of k-edge-deficient temporal graphs." Acta Informatica 59, no. 4 (August 2022): 387–407. http://dx.doi.org/10.1007/s00236-022-00421-5.
Повний текст джерелаАнотація:
AbstractA temporal graph with lifetime L is a sequence of L graphs $$G_1, \ldots ,G_L$$ G 1 , … , G L , called layers, all of which have the same vertex set V but can have different edge sets. The underlying graph is the graph with vertex set V that contains all the edges that appear in at least one layer. The temporal graph is always connected if each layer is a connected graph, and it is k-edge-deficient if each layer contains all except at most k edges of the underlying graph. For a given start vertex s, a temporal exploration is a temporal walk that starts at s, traverses at most one edge in each layer, and visits all vertices of the temporal graph. We show that always-connected, k-edge-deficient temporal graphs with sufficient lifetime can always be explored in $$O(kn \log n)$$ O ( k n log n ) time steps. We also construct always-connected, k-edge-deficient temporal graphs for which any exploration requires $$\varOmega (n \log k)$$ Ω ( n log k ) time steps. For always-connected, 1-edge-deficient temporal graphs, we show that O(n) time steps suffice for temporal exploration.
23
TAMASSIA, ROBERTO, IOANNIS G. TOLLIS, and JEFFREY SCOTT VITTER. "A Parallel Algorithm for Planar Orthogonal Grid Drawings." Parallel Processing Letters 10, no. 01 (March 2000): 141–50. http://dx.doi.org/10.1142/s0129626400000147.
Повний текст джерелаАнотація:
In this paper we consider the problem of constructing planar orthogonal grid drawings (or more simply, layouts) of graphs, with the goal of minimizing the number of bends along the edges. We present optimal parallel algorithms that construct graph layouts with O(n) maximum edge length, O(n2) area, and at most 2n+4 bends (for biconnected graphs) and 2.4n+2 bends (for simply connected graphs). All three of these quality measures for the layouts are optimal in the worst case for biconnected graphs. The algorithm runs on a CREW PRAM in O( log n) time with n/ log n processors, thus achieving optimal time and processor utilization. Applications include VLSI layout, graph drawing, and wireless communication.
24
Hayat, Khizar, Muhammad Irfan Ali, Bing-Yuan Cao, and Xiao-Peng Yang. "A New Type-2 Soft Set: Type-2 Soft Graphs and Their Applications." Advances in Fuzzy Systems 2017 (2017): 1–17. http://dx.doi.org/10.1155/2017/6162753.
Повний текст джерелаАнотація:
The correspondence between a vertex and its neighbors has an essential role in the structure of a graph. Type-2 soft sets are also based on the correspondence of primary parameters and underlying parameters. In this study, we present an application of type-2 soft sets in graph theory. We introduce vertex-neighbors based type-2 soft sets overX(set of all vertices of a graph) andE(set of all edges of a graph). Moreover, we introduce some type-2 soft operations in graphs by presenting several examples to demonstrate these new concepts. Finally, we describe an application of type-2 soft graphs in communication networks and present procedure as an algorithm.
25
Anderson, Jacob, and Geoffrey A. Hollinger. "Communication Planning for Cooperative Terrain-Based Underwater Localization." Sensors 21, no. 5 (March 1, 2021): 1675. http://dx.doi.org/10.3390/s21051675.
Повний текст джерелаАнотація:
This paper presents a decentralized communication planning algorithm for cooperative terrain-based navigation (dec-TBN) with autonomous underwater vehicles. The proposed algorithm uses forward simulation to approximate the value of communicating at each time step. The simulations are used to build a directed acyclic graph that can be searched to provide a minimum cost communication schedule. Simulations and field trials are used to validate the algorithm. The simulations use a real-world bathymetry map from Lake Nighthorse, CO, and a sensor model derived from an Ocean Server Iver2 vehicle. The simulation results show that the algorithm finds a communication schedule that reduces communication bandwidth by 86% and improves robot localization by up to 27% compared to non-cooperative terrain-based navigation. Field trials were conducted in Foster Reservoir, OR, using two Riptide Autonomous Solutions micro-unmanned underwater vehicles. The vehicles collected GPS, altimeter, acoustic communications, and dead reckoning data while following paths on the surface of the reservoir. The data were used to evaluate the planning algorithm. In three of four missions, the planning algorithm improved dec-TBN localization while reducing acoustic communication bandwidth by 56%. In the fourth mission, dec-TBN performed better when using full communications bandwidth, but the communication policy for that mission maintained 86% of the localization accuracy while using 9% of the communications. These results indicate that the presented communication planning algorithm can maintain or improve dec-TBN accuracy while reducing the number of communications used for localization.
26
Preston, Ronald V., and Amanda S. Garner. "Representation as a Vehicle for Solving and Communication." Mathematics Teaching in the Middle School 9, no. 1 (September 2003): 38–43. http://dx.doi.org/10.5951/mtms.9.1.0038.
Повний текст джерелаАнотація:
Students in MS. Simpson's seventh-grade prealgebra class were challenged to use data to decide which of several class party plans was best. Because Takisha focused on price, she preferred using a table to justify her decision. Samantha used a written explanation to determine for herself which plan was best. Brandon's group used a table that indicated the price per person. However, when it came to convincing others of the best plan, some students chose other representations. For example, Brandon decided to use his graphing calculator to display linear graphs of the three plans. Melissa decided to use a triple bar graph. Tables, written explanations, rules, equations, and graphs were all important representations used to solve and communicate the results of the problem.
27
Zhou, Xiaoqing, Mustafa Habib, Tariq Javeed Zia, Asim Naseem, Anila Hanif, and Ansheng Ye. "Topological invariants for the line graphs of some classes of graphs." Open Chemistry 17, no. 1 (December 31, 2019): 1483–90. http://dx.doi.org/10.1515/chem-2019-0154.
Повний текст джерелаАнотація:
AbstractGraph theory plays important roles in the fields of electronic and electrical engineering. For example, it is critical in signal processing, networking, communication theory, and many other important topics. A topological index (TI) is a real number attached to graph networks and correlates the chemical networks with physical and chemical properties, as well as with chemical reactivity. In this paper, our aim is to compute degree-dependent TIs for the line graph of the Wheel and Ladder graphs. To perform these computations, we first computed M-polynomials and then from the M-polynomials we recovered nine degree-dependent TIs for the line graph of the Wheel and Ladder graphs.
28
Draief, M., A. Ganesh, and L. Massoulié. "Exponential Random Graphs as Models of Overlay Networks." Journal of Applied Probability 46, no. 1 (March 2009): 199–220. http://dx.doi.org/10.1239/jap/1238592125.
Повний текст джерелаАнотація:
In this paper we give an analytic solution for graphs withnnodes andE=cnlognedges for which the probability of obtaining a given graphGisµn(G) = exp (-β∑i=1ndi2), wherediis the degree of nodei. We describe how this model appears in the context of load balancing in communication networks, namely peer-to-peer overlays. We then analyse the degree distribution of such graphs and show that the degrees are concentrated around their mean value. Finally, we derive asymptotic results for the number of edges crossing a graph cut and use these results (i) to compute the graph expansion and conductance, and (ii) to analyse the graph resilience to random failures.
29
Saha, Arindam, James A. R. Marshall, and Andreagiovanni Reina. "Memory and communication efficient algorithm for decentralized counting of nodes in networks." PLOS ONE 16, no. 11 (November 22, 2021): e0259736. http://dx.doi.org/10.1371/journal.pone.0259736.
Повний текст джерелаАнотація:
Node counting on a graph is subject to some fundamental theoretical limitations, yet a solution to such problems is necessary in many applications of graph theory to real-world systems, such as collective robotics and distributed sensor networks. Thus several stochastic and naïve deterministic algorithms for distributed graph size estimation or calculation have been provided. Here we present a deterministic and distributed algorithm that allows every node of a connected graph to determine the graph size in finite time, if an upper bound on the graph size is provided. The algorithm consists in the iterative aggregation of information in local hubs which then broadcast it throughout the whole graph. The proposed node-counting algorithm is on average more efficient in terms of node memory and communication cost than its previous deterministic counterpart for node counting, and appears comparable or more efficient in terms of average-case time complexity. As well as node counting, the algorithm is more broadly applicable to problems such as summation over graphs, quorum sensing, and spontaneous hierarchy creation.
30
GU, WEIZHEN, and KIRSTI WASH. "BOUNDS ON THE DOMINATION NUMBER OF PERMUTATION GRAPHS." Journal of Interconnection Networks 10, no. 03 (September 2009): 205–17. http://dx.doi.org/10.1142/s0219265909002522.
Повний текст джерелаАнотація:
For a graph G with n vertices and a permutation α on V(G), a permutation graph Pα(G) is obtained from two identical copies of G by adding an edge between v and α(V) for any v ϵ V(G). Let γ(G) be the domination number of a graph G. It has been shown that γ(G) ≤ γ(Pα(G) ≤ 2γ(G) for any permutation α on V(G). In this paper, we investigate specific graphs for which there exists a permutation α such that γ(Pα(G)) ≻ γ(G) in terms of the domination number of G or the maximum degree of G. Additionally, we construct a class of graphs for which the domination number of any permutation graph is twice the domination number of the original graph, as well as explore finding a specific graph G and permutation α for any two positive integers a and b with a ≤ b ≤ 2a, to have γ(G) = a and γ(Pα(G)) = b.
31
BHABAK, PUSPAL, and HOVHANNES A. HARUTYUNYAN. "Approximation Algorithm for the Broadcast Time in k-Path Graph." Journal of Interconnection Networks 19, no. 04 (December 2019): 1950006. http://dx.doi.org/10.1142/s0219265919500063.
Повний текст джерелаАнотація:
Broadcasting is an information dissemination problem in a connected network in which one node, called the originator, must distribute a message to all other nodes by placing a series of calls along the communication lines of the network. In every unit of time, the informed nodes aid the originator in distributing the message. Finding the broadcast time of any vertex in an arbitrary graph is NP-complete. The polynomial time solvability is shown only for certain graphs like trees, unicyclic graphs, tree of cycles, necklace graphs, fully connected trees and tree of cliques. In this paper we study the broadcast problem in k-path graphs. For any originator of the k-path graph we present a (4 – ϵ)-approximation algorithm in the worst case. The algorithm gives a better approximation ratio for some large classes of k-path graphs. Moreover, our algorithm generates the optimal broadcast time for some cases.
32
Draief, M., A. Ganesh, and L. Massoulié. "Exponential Random Graphs as Models of Overlay Networks." Journal of Applied Probability 46, no. 01 (March 2009): 199–220. http://dx.doi.org/10.1017/s0021900200005313.
Повний текст джерелаАнотація:
In this paper we give an analytic solution for graphs with n nodes and E = cn log n edges for which the probability of obtaining a given graph G is µn (G) = exp (- β ∑i=1 n d i 2), where d i is the degree of node i. We describe how this model appears in the context of load balancing in communication networks, namely peer-to-peer overlays. We then analyse the degree distribution of such graphs and show that the degrees are concentrated around their mean value. Finally, we derive asymptotic results for the number of edges crossing a graph cut and use these results (i) to compute the graph expansion and conductance, and (ii) to analyse the graph resilience to random failures.
33
Zeng, Yong, Yixin Li, Zhongyuan Jiang, and Jianfeng Ma. "GNS: Forge High Anonymity Graph by Nonlinear Scaling Spectrum." Security and Communication Networks 2021 (September 30, 2021): 1–11. http://dx.doi.org/10.1155/2021/8609278.
Повний текст джерелаАнотація:
It is crucial to generate random graphs with specific structural properties from real graphs, which could anonymize graphs or generate targeted graph data sets. The state-of-the-art method called spectral graph forge (SGF) was proposed at INFOCOM 2018. This method uses a low-rank approximation of the matrix by throwing away some spectrums, which provides privacy protection after distributing graphs while ensuring data availability to a certain extent. As shown in SGF, it needs to discard at least 20% spectrum to defend against deanonymous attacks. However, the data availability will be significantly decreased after more spectrum discarding. Thus, is there a way to generate a graph that guarantees maximum spectrum and anonymity at the same time? To solve this problem, this paper proposes graph nonlinear scaling (GNS). We firmly prove that GNS can preserve all eigenvectors meanwhile providing high anonymity for the forged graph. Precisely, the GNS scales the eigenvalues of the original spectrum and constructs the forged graph with scaled eigenvalues and original eigenvectors. This approach maximizes the preservation of spectrum information to guarantee data availability. Meanwhile, it provides high robustness towards deanonymous attacks. The experimental results show that when SGF discards only 10% of the spectrum, the forged graph has high data availability. At this time, if the distance vector deanonymity algorithm is used to attack the forged graph, almost 100% of the nodes can be identified, while when achieving the same availability, only about 20% of the nodes in the forged graph obtained from GNS can be identified. Moreover, our method is better than SGF in capturing the real graph’s structure in terms of modularity, the number of partitions, and average clustering.
34
Jarrar, Mustafa, and Anton Deik. "The Graph Signature." International Journal on Semantic Web and Information Systems 11, no. 2 (April 2015): 36–65. http://dx.doi.org/10.4018/ijswis.2015040102.
Повний текст джерелаАнотація:
Querying large data graphs has brought the attention of the research community. Many solutions were proposed, such as Oracle Semantic Technologies, Virtuoso, RDF3X, and C-Store, among others. Although such approaches have shown good performance in queries with medium complexity, they perform poorly when the complexity of the queries increases. In this paper, the authors propose the Graph Signature Index, a novel and scalable approach to index and query large data graphs. The idea is that they summarize a graph and instead of executing the query on the original graph, they execute it on the summaries. The authors' experiments with Yago (16M triples) have shown that e.g., a query with 4 levels costs 62 sec using Oracle but it only costs about 0.6 sec with their index. Their index can be implemented on top of any Graph database, but they chose to implement it as an extension to Oracle on top of the SEM_MATCH table function. The paper also introduces disk-based versions of the Trace Equivalence and Bisimilarity algorithms to summarize data graphs, and discusses their complexity and usability for RDF graphs.
35
LIN, LAN, and YIXUN LIN. "The Minimum Stretch Spanning Tree Problem for Hamming Graphs and Higher-Dimensional Grids." Journal of Interconnection Networks 20, no. 01 (March 2020): 2050004. http://dx.doi.org/10.1142/s0219265920500048.
Повний текст джерелаАнотація:
The minimum stretch spanning tree problem for a graph G is to find a spanning tree T of G such that the maximum distance in T between two adjacent vertices is minimized. The minimum value of this optimization problem gives rise to a graph invariant σ(G), called the tree-stretch of G. The problem has been proved NP-hard. In this paper we present a general approach to determine the exact values σ(G) for a series of typical graphs arising from communication networks, such as Hamming graphs and higher-dimensional grids (including hypercubes).
36
ZHANG, YINGYING, and XIAOYU ZHU. "Proper Vertex Connection and Graph Operations." Journal of Interconnection Networks 19, no. 02 (June 2019): 1950001. http://dx.doi.org/10.1142/s0219265919500014.
Повний текст джерелаАнотація:
A path in a vertex-colored graph is a vertex-proper path if any two internal adjacent vertices differ in color. A vertex-colored graph is proper vertex k-connected if any two vertices of the graph are connected by k disjoint vertex-proper paths of the graph. For a k-connected graph G, the proper vertex k-connection number of G, denoted by pvck(G), is defined as the smallest number of colors required to make G proper vertex k-connected. A vertex-colored graph is strong proper vertex-connected, if for any two vertices u, v of the graph, there exists a vertex-proper u-v geodesic. For a connected graph G, the strong proper vertex-connection number of G, denoted by spvc(G), is the smallest number of colors required to make G strong proper vertex-connected. In this paper, we study the proper vertex k-connection number and the strong proper vertex-connection number on the join of two graphs, the Cartesian, lexicographic, strong and direct product, and present exact values or upper bounds for these operations of graphs. Then we apply these results to some instances of Cartesian and lexicographic product networks.
37
Atkins, Rachel M., and Karen S. McNeal. "Exploring Differences Among Student Populations During Climate Graph Reading Tasks: An Eye Tracking Study." Journal of Astronomy & Earth Sciences Education (JAESE) 5, no. 2 (December 4, 2018): 85–114. http://dx.doi.org/10.19030/jaese.v5i2.10219.
Повний текст джерелаАнотація:
Communicating climate information is challenging due to the interdisciplinary nature of the topic along with compounding cognitive and affective learning challenges. Graphs are a common representation used by scientists to communicate evidence of climate change. However, it is important to identify how and why individuals on the continuum of expertise navigate graphical data differently as this has implications for effective communication of this information. We collected and analyzed eye-tracking metrics of geoscience graduate students and novice undergraduate students while viewing graphs displaying climate information. Our findings indicate that during fact-extraction tasks, novice undergraduates focus proportionally more attention on the question, title and axes graph elements, whereas geoscience graduate students spend proportionally more time viewing and interpreting data. This same finding was enhanced during extrapolation tasks. Undergraduate novices were also more likely to describe general trends, while graduate students identified more specific patterns. Undergraduates who performed high on the pre-test measuring graphing skill, viewed graphs more similar to graduate students than their peers who performed lower on the pre-test.
38
Min, Seung Won, Kun Wu, Sitao Huang, Mert Hidayetoğlu, Jinjun Xiong, Eiman Ebrahimi, Deming Chen, and Wen-mei Hwu. "Large graph convolutional network training with GPU-oriented data communication architecture." Proceedings of the VLDB Endowment 14, no. 11 (July 2021): 2087–100. http://dx.doi.org/10.14778/3476249.3476264.
Повний текст джерелаАнотація:
Graph Convolutional Networks (GCNs) are increasingly adopted in large-scale graph-based recommender systems. Training GCN requires the minibatch generator traversing graphs and sampling the sparsely located neighboring nodes to obtain their features. Since real-world graphs often exceed the capacity of GPU memory, current GCN training systems keep the feature table in host memory and rely on the CPU to collect sparse features before sending them to the GPUs. This approach, however, puts tremendous pressure on host memory bandwidth and the CPU. This is because the CPU needs to (1) read sparse features from memory, (2) write features into memory as a dense format, and (3) transfer the features from memory to the GPUs. In this work, we propose a novel GPU-oriented data communication approach for GCN training, where GPU threads directly access sparse features in host memory through zero-copy accesses without much CPU help. By removing the CPU gathering stage, our method significantly reduces the consumption of the host resources and data access latency. We further present two important techniques to achieve high host memory access efficiency by the GPU: (1) automatic data access address alignment to maximize PCIe packet efficiency, and (2) asynchronous zero-copy access and kernel execution to fully overlap data transfer with training. We incorporate our method into PyTorch and evaluate its effectiveness using several graphs with sizes up to 111 million nodes and 1.6 billion edges. In a multi-GPU training setup, our method is 65--92% faster than the conventional data transfer method, and can even match the performance of all-in-GPU-memory training for some graphs that fit in GPU memory.
39
Li, Zitong, Xiang Cheng, Lixiao Sun, Ji Zhang, and Bing Chen. "A Hierarchical Approach for Advanced Persistent Threat Detection with Attention-Based Graph Neural Networks." Security and Communication Networks 2021 (May 4, 2021): 1–14. http://dx.doi.org/10.1155/2021/9961342.
Повний текст джерелаАнотація:
Advanced Persistent Threats (APTs) are the most sophisticated attacks for modern information systems. Currently, more and more researchers begin to focus on graph-based anomaly detection methods that leverage graph data to model normal behaviors and detect outliers for defending against APTs. However, previous studies of provenance graphs mainly concentrate on system calls, leading to difficulties in modeling network behaviors. Coarse-grained correlation graphs depend on handcrafted graph construction rules and, thus, cannot adequately explore log node attributes. Besides, the traditional Graph Neural Networks (GNNs) fail to consider meaningful edge features and are difficult to perform heterogeneous graphs embedding. To overcome the limitations of the existing approaches, we present a hierarchical approach for APT detection with novel attention-based GNNs. We propose a metapath aggregated GNN for provenance graph embedding and an edge enhanced GNN for host interactive graph embedding; thus, APT behaviors can be captured at both the system and network levels. A novel enhancement mechanism is also introduced to dynamically update the detection model in the hierarchical detection framework. Evaluations show that the proposed method outperforms the state-of-the-art baselines in APT detection.
40
Zeen El Deen, Mohamed R., and Ghada Elmahdy. "New classes of graphs with edge $ \; \delta- $ graceful labeling." AIMS Mathematics 7, no. 3 (2022): 3554–89. http://dx.doi.org/10.3934/math.2022197.
Повний текст джерелаАнотація:
<abstract><p>Graph labeling is a source of valuable mathematical models for an extensive range of applications in technologies (communication networks, cryptography, astronomy, data security, various coding theory problems). An edge $ \; \delta - $ graceful labeling of a graph $ G $ with $ p\; $ vertices and $ q\; $ edges, for any positive integer $ \; \delta $, is a bijective $ \; f\; $ from the set of edge $ \; E(G)\; $ to the set of positive integers $ \; \{ \delta, \; 2 \delta, \; 3 \delta, \; \cdots\; , \; q\delta\; \} $ such that all the vertex labels $ \; f^{\ast} [V(G)] $, given by: $ f^{\ast}(u) = (\sum\nolimits_{uv \in E(G)} f(uv)\; )\; mod\; (\delta \; k) $, where $ k = max (p, q) $, are pairwise distinct. In this paper, we show the existence of an edge $ \; \delta- $ graceful labeling, for any positive integer $ \; \delta $, for the following graphs: the splitting graphs of the cycle, fan, and crown, the shadow graphs of the path, cycle, and fan graph, the middle graphs and the total graphs of the path, cycle, and crown. Finally, we display the existence of an edge $ \; \delta- $ graceful labeling, for the twig and snail graphs.</p></abstract>
41
RAFE, VAHID, and ADEL T. RAHMANI. "A NOVEL APPROACH TO VERIFY GRAPH SCHEMA-BASED SOFTWARE SYSTEMS." International Journal of Software Engineering and Knowledge Engineering 19, no. 06 (September 2009): 857–70. http://dx.doi.org/10.1142/s0218194009004398.
Повний текст джерелаАнотація:
Graph Grammars have recently become more and more popular as a general formal modeling language. Behavioral modeling of dynamic systems and model to model transformations are a few well-known examples in which graphs have proven their usefulness in software engineering. A special type of graph transformation systems is layered graphs. Layered graphs are a suitable formalism for modeling hierarchical systems. However, most of the research so far concentrated on graph transformation systems as a modeling means, without considering the need for suitable analysis tools. In this paper we concentrate on how to analyze these models. We will describe our approach to show how one can verify the designed graph transformation systems. To verify graph transformation systems we use a novel approach: using Bogor model checker to verify graph transformation systems. The AGG-like graph transformation systems are translated to BIR — the input language of Bogor — and Bogor verifies that model against some properties defined by combining LTL and special purpose graph rules. Supporting schema-based and layered graphs characterize our approach among existing solutions for verification of graph transformation systems.
42
Ni, Xiang, Jing Li, Mo Yu, Wang Zhou, and Kun-Lung Wu. "Generalizable Resource Allocation in Stream Processing via Deep Reinforcement Learning." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 01 (April 3, 2020): 857–64. http://dx.doi.org/10.1609/aaai.v34i01.5431.
Повний текст джерелаАнотація:
This paper considers the problem of resource allocation in stream processing, where continuous data flows must be processed in real time in a large distributed system. To maximize system throughput, the resource allocation strategy that partitions the computation tasks of a stream processing graph onto computing devices must simultaneously balance workload distribution and minimize communication. Since this problem of graph partitioning is known to be NP-complete yet crucial to practical streaming systems, many heuristic-based algorithms have been developed to find reasonably good solutions. In this paper, we present a graph-aware encoder-decoder framework to learn a generalizable resource allocation strategy that can properly distribute computation tasks of stream processing graphs unobserved from training data. We, for the first time, propose to leverage graph embedding to learn the structural information of the stream processing graphs. Jointly trained with the graph-aware decoder using deep reinforcement learning, our approach can effectively find optimized solutions for unseen graphs. Our experiments show that the proposed model outperforms both METIS, a state-of-the-art graph partitioning algorithm, and an LSTM-based encoder-decoder model, in about 70% of the test cases.
43
LÜ, HUAZHONG, and TINGZENG WU. "Fractional Matching Preclusion for Restricted Hypercube-Like Graphs." Journal of Interconnection Networks 19, no. 03 (September 2019): 1940010. http://dx.doi.org/10.1142/s0219265919400103.
Повний текст джерелаАнотація:
The restricted hypercube-like graphs, variants of the hypercube, were proposed as desired interconnection networks of parallel systems. The matching preclusion number of a graph is the minimum number of edges whose deletion results in the graph with neither perfect matchings nor almost perfect matchings. The fractional perfect matching preclusion and fractional strong perfect matching preclusion are generalizations of the matching preclusion. In this paper, we obtain fractional matching preclusion number and fractional strong matching preclusion number of restricted hypercube-like graphs, which extend some known results.
44
Mufti, Zeeshan Saleem, Eiman Fatima, Rukhshanda Anjum, Fairouz Tchier, Qin Xin, and Md Moyazzem Hossain. "Computing First and Second Fuzzy Zagreb Indices of Linear and Multiacyclic Hydrocarbons." Journal of Function Spaces 2022 (March 22, 2022): 1–8. http://dx.doi.org/10.1155/2022/6281592.
Повний текст джерелаАнотація:
Fuzzy graph theory was invented by Rosenfeld. It is the extension of the work of L.A. Zadeh on fuzzy sets. Rosenfeld extracted the fuzzy-related concepts using the graph theoretic concepts. Topological indices for crisp theory have already been discussed in the literature but these days, topological index-related fuzzy graphs are much popular. Fuzzy graphs are being used as an application in different fields of sciences such as broadcast, communications, producing, social network, man-made reasoning, data hypothesis, and neural systems. In this paper, we have computed some fuzzy topological indices such as first and second Zagreb indices, Randic index, and harmonic index of fuzzy chemical graph named phenylene.
45
Marbel, Revital, Boaz Ben-Moshe, and Tal Grinshpoun. "Urban Free-Space Optical Network Optimization." Applied Sciences 10, no. 21 (November 6, 2020): 7872. http://dx.doi.org/10.3390/app10217872.
Повний текст джерелаАнотація:
This paper presents a set of graph optimization problems related to free-space optical communication networks. Such laser-based wireless networks require a line of sight to enable communication, thus a visibility graph model is used herein. The main objective is to provide connectivity from a communication source point to terminal points through the use of some subset of available intermediate points. To this end, we define a handful of problems that differ mainly in the costs applied to the nodes and/or edges of the graph. These problems should be optimized with respect to cost and performance. The problems at hand are shown to be NP-hard. A generic heuristic based on a genetic algorithm is proposed, followed by a set of simulation experiments that demonstrate the performance of the suggested heuristic method on real-life scenarios. The suggested genetic algorithm is compared with the Euclidean Steiner tree method. Our simulations show that in many settings, especially in dense graphs, the genetic algorithm finds lower-cost solutions than its competitor, while it falls behind in some settings. However, the run-time performance of the genetic algorithm is considerably better in graphs with 1000 nodes or more, being more than twice faster in some settings. We conclude that the suggested heuristic improves run-time performance on large-scale graphs and can handle a wider range of related optimization problems. The simulation results suggest that the 5G urban backbone may benefit significantly from using free-space optical networks.
46
OBRENIĆ, BOJANA. "APPROXIMATING HYPERCUBES BY INDEX-SHUFFLE GRAPHS VIA DIRECT-PRODUCT EMULATIONS." Journal of Interconnection Networks 05, no. 04 (December 2004): 429–73. http://dx.doi.org/10.1142/s0219265904001258.
Повний текст джерелаАнотація:
Index-shuffle graphs are a family of bounded-degree hypercube-like interconnection networks for parallel computers, introduced by [Baumslag and Obrenić (1997): Index-Shuffle Graphs, …], as an efficient substitute for two standard families of hypercube derivatives: butterflies and shuffle-exchange graphs. In the theoretical framework of graph embedding and network emulations, this paper shows that the index-shuffle graph efficiently approximates the direct-product structure of the hypercube, and thereby has a unique potential to approximate efficiently all of its derivatives. One of the consequences of our results is that any member of the following group of standard bounded-degree hypercube derivatives: butterflies, shuffles, tori, meshes of trees, is emulated by the index-shuffle graph with a slowdown in the order of the logarithm of the slowdown of the most efficient emulation achieved by any other member of this group. Emulation algorithms are presented where the emulation host is the n-dimensional index-shuffle graph Ψn, having N=2n nodes. The emulated graph G is a direct product of the form: G=F0×F1×⋯×Fk-1 where k is a power of 2, and each factor Fi is an instance of any of the following three graph families: cycle, complete binary tree, X-tree. Let the size of each factor be |Fi|≤2nf, where k·nf≤n. The index-shuffle graph Ψn, emulates any factor Fi in the product G with slowdown: O( log k) + O( log nf), which is O( log n) = O( log log N). Any collection of 2ℓ copies of the product G, such that: ℓ+k·nf≤n is emulated by the index-shuffle graph Ψn simultaneously, without any additional slowdown. Relaxing the assumption that k is a power of 2 introduces an additional factor of O( lg *N) into the slowdown.
47
Cyman, Joanna, and Joanna Raczek. "Application of Doubly Connected Dominating Sets to Safe Rectangular Smart Grids." Energies 15, no. 9 (April 19, 2022): 2969. http://dx.doi.org/10.3390/en15092969.
Повний текст джерелаАнотація:
Smart grids, together with the Internet of Things, are considered to be the future of the electric energy world. This is possible through a two-way communication between nodes of the grids and computer processing. It is necessary that the communication is easy and safe, and the distance between a point of demand and supply is short, to reduce the electricity loss. All these requirements should be met at the lowest possible cost. In this paper, we study a two-dimensional rectangular grid graph which is considered to be a model of a smart grid; nodes of the graph represent points and devices of the smart grid, while links represent possible ways of communication and energy transfer. We consider the problem of choosing the lowest possible number of locations (nodes, points) of the grid which could serve as energy sources (or a source of different resources) to other nodes in such a way that we ensure reduction in electricity loss and provide safe communication and resistance to failures and increases in energy demand.Therefore, we study minimum doubly connected dominating sets in grid graphs. We show that the proposed solutions are the best possible in terms of the number of source points for the case of narrow grid graphs and we give upper and lower bounds for the case of wide grid graphs.
48
Antonio, Yeftanus, Sapto Wahyu Indratno, and Rinovia Simanjuntak. "Cyber Insurance Ratemaking: A Graph Mining Approach." Risks 9, no. 12 (December 6, 2021): 224. http://dx.doi.org/10.3390/risks9120224.
Повний текст джерелаАнотація:
Cyber insurance ratemaking (CIRM) is a procedure used to set rates (or prices) for cyber insurance products provided by insurance companies. Rate estimation is a critical issue for cyber insurance products. This problem arises because of the unavailability of actuarial data and the uncertainty of normative standards of cyber risk. Most cyber risk analyses do not consider the connection between Information Communication and Technology (ICT) sources. Recently, a cyber risk model was developed that considered the network structure. However, the analysis of this model remains limited to an unweighted network. To address this issue, we propose using a graph mining approach (GMA) to CIRM, which can be applied to obtain fair and competitive prices based on weighted network characteristics. This study differs from previous studies in that it adds the GMA to CIRM and uses communication models to explain the frequency of communications as weights in the network. We used the heterogeneous generalized susceptible-infectious-susceptible model to accommodate different infection rates. Our approach adds up to the existing method because it considers the communication frequency and GMA in CIRM. This approach results in heterogeneous premiums. Additionally, GMA can choose more active communications to reflect high communications contribution in the premiums or rates. This contribution is not found when the infection rates are the same. Based on our experimental results, it is apparent that this method can produce more reasonable and competitive prices than other methods. The prices obtained with GMA and communication factors are lower than those obtained without GMA and communication factors.
49
MAO, YAPING, ZHIWEI GUO, NAN JIA, and HE LI. "Lineark-Arboricity in Product Networks." Journal of Interconnection Networks 16, no. 03n04 (September 2016): 1650008. http://dx.doi.org/10.1142/s0219265916500080.
Повний текст джерелаАнотація:
A linear k-forest is a forest whose components are paths of length at most k. The linear k-arboricity of a graph G, denoted bylak(G), is the least number of linear k-forests needed to decompose G. Recently, Zuo, He, and Xue studied the exact values of the linear(n−1)-arboricity of Cartesian products of various combinations of complete graphs, cycles, complete multipartite graphs. In this paper, for general k we show thatmax{lak(G),lal(H)}≤lamax{k,l}(G□H)≤lak(G)+lal(H)for any two graphs G and H. Denote byG∘H, G×HandG⊠Hthe lexicographic product, direct product and strong product of two graphs G and H, respectively. For any two graphs G and H, we also derive upper and lower bounds oflak(G∘H),lak(G×H)andlak(G⊠H)in this paper. The linear k-arboricity of a 2-dimensional grid graph, a r-dimensional mesh, a r-dimensional torus, a r-dimensional generalized hypercube and a hyper Petersen network are also studied.
50
Cao, Jian Xiang, Xin Feng, and Zheng Tao Jiang. "On the Graph Parameters of Special Networks." Applied Mechanics and Materials 543-547 (March 2014): 2977–80. http://dx.doi.org/10.4028/www.scientific.net/amm.543-547.2977.
Повний текст джерелаАнотація:
Domination in graphs has become one of the major areas of graph theory with extensive applications in design and analysis of communication networks, computational complexity, and algorithm design. This paper mainly research on domination number and bondage number of the graph, especially, these parameters measure to some extent the robustness of an interconnection network with respect to link failures. By constructing a family of minimum dominating sets we compute the domination number and bondage number of the sun graph.