China
Africa
Explore chapters and articles related to this topic
The exact complexity of the Tutte polynomial
Published in Joanna A. Ellis-Monaghan, Iain Moffatt, Handbook of the Tutte Polynomial and Related Topics, 2022
Tomer Kotek, Johann A. Makowsky
Typical families of functions in VNP are generating functions of graph properties. These are polynomials depending on graphs with indeterminate weights on the edges. Let P be a graph property, i.e., a class of finite graphs closed under isomorphisms. For a graph G=(V,E) the generating function of a graph property is GF(G,P)=∑∏e∈AXe,
DTN Coding
Published in Aloizio Pereira da Silva, Scott Burleigh, Katia Obraczka, Delay and Disruption Tolerant Networks, 2019
Marius Feldmann, Felix Walter, Tomaso de Cola, Gianluigi Liva
Another graph property that will condition the performance of an LDPC code under iterative decoding is the graph girth. A cycle in a bipartite graph is a sequence of edges leading to closed path where each node belonging to the cycle is visited once. The length of a cycle is given by the number of edges composing the cycle. The girth g of graph G is the length of its shortest cycle.
Modeling and Simulation Tools for Mobile Ad Hoc Networks
Published in Jonathan Loo, Jaime Lloret Mauri, Jesús Hamilton Ortiz, Mobile Ad Hoc Networks, 2016
Kayhan Erciyes, Orhan Dagdeviren, Deniz Cokuslu, Onur Yılmaz, Hasan Gumus
A MANET can be modeled as a graph G(V, E), where V is the set of vertices and E is the set of edges. Two vertices (nodes) of a graph are connected only if there is a communication link between them. Once a MANET is represented as a graph, the next issue at hand is whether any graph property has any implications for the MANET. For example, a dominating set (DS) D of a graph is the set of vertices where a vertex v ϵ V is either in D or adjacent to a vertex in D. If vertices of a DS are connected, the DS is called a connected dominating set (CDS), and forming a CDS in the graph model of the MANET provides a communication backbone for routing purposes in the actual mobile network. However, finding a minimum DS or a CDS is an NP-complete problem in graph theory, and hence approximation algorithms for such problems where suboptimal solutions using some heuristics are usually the only choice. However, designing an approximation algorithm with a favorable approximation ratio to the optimum solution to the problem is not sufficient, since one is dealing with a real network without any global information. Any algorithm employed must be distributed without any global knowledge. A distributed algorithm is run by all nodes of a MANET, provides exchange of information with its neighbor nodes by message passing only, and eventually results in reaching a determined state of the network [1]. Based on the above discussion, the challenge is in fact designing of distributed approximation algorithm with a favorable approximation ratio that can be implemented on the graph model of the MANET, which provides a solution to a graph problem that is usually extremal and has implications in the real MANET environment. Some other real-life considerations such as the battery lifetime of nodes in sensor networks or the mobility of the nodes in a MANET may have to be incorporated to the distributed approximation algorithm as the final adjustment.
Distributed maximal independent set computation driven by finite-state dynamics
Published in International Journal of Parallel, Emergent and Distributed Systems, 2023
Eric Goles, Laura Leal, Pedro Montealegre, Ivan Rapaport, Martín Ríos-Wilson
A graph property is called an hereditary property if it is closed under taking induced subgraphs. An example of a hereditary property is bounded degeneracy. A graph G is called d-degenerate if every subgraph of G (including G itself) contains a vertex of degree at most d. Alternatively, a graph has degeneracy d if it can be decomposed successively removing vertices of degree at most d. In the following lemma, we now show that in a d-degenerate graph, for most vertices their degree is bounded by 4d−2.
A practical analysis of sample complexity for structure learning of discrete dynamic Bayesian networks
Published in Optimization, 2022
Based on Equation (7), the score of a model can be decomposed to the score of individual nodes. The score of each node is called the family score of that node, and the total score is defined as follows: The score decomposability has one significant advantage for learning algorithms: it provides a local search to find the best model [44]. Maximizing the score of a model is just maximizing the family score of each node. Therefore, the search space of dDBN is limited to . In the learning procedure, possible parents of each node are scored, and the one with the highest score is assigned as the parents of that node. For a higher number of nodes, this method would not be feasible, because search space is exponentially growing with the number of nodes. In this case, heuristic search methods could be used for finding the most likely graph to represent the data. In this study, we had not considered any heuristic method because the aim of the study was to analyse the effect of the number of samples on the learned model. The issues regarding the heuristic methods had to be omitted to obtain a reliable result; because they may have effects on the learned structure, not depending on the number of samples but depending on the searching algorithm. Besides, due to the score decomposability property, the corresponding searching algorithm is only applicable for DBNs, not for any generic BNs. Because when a parent set of one node is learned, the resultant parents of that node most probably will limit the possible parent set of other nodes. The reason behind this limitation is the directed acyclic graph property of BNs. We may not add a new parent to a particular node if it violates the DAG property due to pre-found parents of the other nodes. This searching technique may be feasible for BNs if the order of the nodes is known by prior information [22,44], which is indeed not a realistic case. However, DBNs always guarantee DAG property due to its design, hence for dDBNs.
Improved formulations of the joint order batching and picker routing problem
Published in International Journal of Production Research, 2022
In this subsection, we derive additional constraints by investigating the graph property of the warehouse. We first restrict our attention to a single-block warehouse. By ‘traversing’, we mean going from the north artificial vertex to the south artificial vertex or vice-versa.