China
Africa
Explore chapters and articles related to this topic
Water Drop Algorithm
Published in Nazmul Siddique, Hojjat Adeli, Nature-Inspired Computing, 2017
The maximum-clique problem (MCP) is a classical graph theory problem, which is considered as an NP-hard optimization problem. A clique C of a graph G is a subset of V such that G(C) is complete. The graph G is an arbitrary directed graph defined by G = 〈V, E〉, where V = {v1, …, vn} is the set of vertices, E ⊆ V × V, E = {(vi, vj)}, i ≠ j, {vi} ∈ V, i,j = 1,2, …, n is the set of edges in G. A positive weight wi is associated with each vertex vi ∈ V. AG = [aij]n×n is an n × n adjacency matrix of graph G where aij = 1 if (vi, vj) ∈ E is an edge and aij = 0 if (vi, vj) ∉ E. For a subset S ⊆ V the weight of S is defined as W(S)=∑vi∈Swi. The subgraph induced by S is defined as G(S) = (S, E∩S × S). Thus, G(C) is complete if all its vertices are pairwise adjacent. The maximum clique then requires G(C) to be of maximum weight (Pardalos and Xue, 1994). The MCP has many formulations, but the simplest is defined as follows: max∑vi∈Cwixiwithxi∈{0,1}
Routing and wavelength assignment with protection: A quadratic unconstrained binary optimization approach enabled by Digital Annealer technology
Published in IISE Transactions, 2023
Oylum Şeker, Merve Bodur, Hamed Pouya
A plausible alternative to tackle such problems is to formulate them as QUBO models and generate solutions via novel computational architectures and new technologies, such as adiabatic quantum computing (e.g., Papalitsas et al., 2019), neuromorphic computing (e.g., Corder et al., 2018), and optical parametric oscillators (e.g., Inagaki et al. 2016), which have recently attracted significant attention due to their capability in tackling combinatorial optimization problems. A promising example to these new technologies is DA (Aramon et al., 2019), which is a computer architecture that rivals quantum computers in utility (Boyd, 2018). DA is designed to solve QUBO models, and uses an algorithm based on simulated annealing. In many applications, such as the minimum vertex cover problem (Javad-Kalbasi et al., 2019), maximum clique problem (Naghsh et al., 2019) and outlier rejection (Rahman et al., 2019), it has been shown to significantly improve upon the state of the art and yield high-quality solutions in radically short amount of time.
A synod based deterministic and indulgent leader election protocol for asynchronous large groups
Published in International Journal of Parallel, Emergent and Distributed Systems, 2022
Sathyanarayanan Srinivasan, Ramesh kandukoori
Consider a WSN as shown in Figure 11. The topology of ad-hoc Wireless communication networks are modelled as unit disc graphs starting from the work of [63]. We model the WSN as a unit disc graph where represents the set of vertices and represents the set of edges. Each sensor node is modelled as a vertex and if two nodes are in the range to communicate with each other in one message delay, then they are connected by an edge. We assume all nodes have equal range to model them as a unit disc graph. We choose an Acceptor set A to be a clique of graph G with size approximately equal to k, the desired number of acceptors. In Figure 11, an example is shown by circling a set of 5 nodes that form a clique. For maximum resiliency and performance, it is optimal to choose the maximum clique in the graph. The maximum clique problem is shown to be solvable in polynomial time in unit disc graphs [64].
A resource-oriented decomposition approach for train timetabling problem with variant running time and minimum headway
Published in Transportation Letters, 2022
Zhengwen Liao, Jianrui Miao, Lingyun Meng, Haiying Li
As an instance of the large-scale time-space resource allocation problem, the train timetabling problem is regarded as the most important practical problem in tactical railway operation management. It specifies the arrival and departure times for each train at all stations along its route, which implicitly denotes the infrastructure utilization of trains. From the perspective of operations research, the train timetabling problem can be model as a job-shop scheduling problem (Szpigel 1973), or a max-clique problem (Caprara, Fischetti, and Toth 2002). Many novel models provide clear and substantial structures of the train timetabling problem, however, neglect some important factors considered in practical timetabling procedures. For example, many train timetabling models assume the running time in open-track segments and the minimum headways are fixed values. However, the scheduled intermediate stops result in additional running time and signal occupation time during the acceleration and deceleration procedure. Besides, when a realistic train timetable is generated, some detailed practical factors (e.g., train speed, stopp-decisions, train priorities, and station capacities) should be considered to increase the feasibility and accuracy.