Explore the vast range of titles available.

We present OIM (Oscillator Ising Machines), a new way to make Ising machines using networks of coupled self-sustaining nonlinear oscillators. OIM is theoretically rooted in a novel result that establishes that the phase dynamics of coupled oscillator systems, under the influence of subharmonic injection locking, are governed by a Lyapunov function that is closely related to the Ising Hamiltonian of the coupling graph. As a result, the dynamics of such oscillator networks evolve naturally to local minima of the Lyapunov function. Two simple additional steps (i.e., turning subharmonic locking on and off smoothly, and adding noise) enable the network to find excellent solutions of Ising problems. We demonstrate our method on Ising versions of the MAX-CUT and graph colouring problems, showing that it improves on previously published results on several problems in the G benchmark set. Using synthetic problems with known global minima, we also present initial scaling results. Our scheme, which is amenable to realisation using many kinds of oscillators from different physical domains, is particularly well suited for CMOS IC implementation, offering significant practical advantages over previous techniques for making Ising machines. We report working hardware prototypes using CMOS electronic oscillators.

Graph colouring is the system of assigning a colour to each vertex of a graph. It is done in such a way that adjacent vertices do not have equal colour. It is fundamental in graph theory. It is often used to solve real-world problems like traffic light signalling, map colouring, scheduling, etc. Nowadays, social networks are prevalent systems in our life. Here, the users are considered as vertices, and their connections/interactions are taken as edges. Some users follow other popular users’ profiles in these networks, and some don’t, but those non-followers are connected directly to the popular profiles. That means, along with traditional relationship (information flowing), there is another relation among them. It depends on the domination of the relationship between the nodes. This type of situation can be modelled as a directed fuzzy graph. In the colouring of fuzzy graph theory, edge membership plays a vital role. Edge membership is a representation of flowing information between end nodes of the edge. Apart from the communication relationship, there may be some other factors like domination in relation. This influence of power is captured here. In this article, the colouring of directed fuzzy graphs is defined based on the influence of relationship. Along with this, the chromatic number and strong chromatic number are provided, and related properties are investigated. An application regarding COVID-19 infection is presented using the colouring of directed fuzzy graphs.

Graph coloring is widely used to parallelize scientific applications by identifying subsets of independent tasks that can be executed simultaneously. Graph coloring assigns colors the vertices of a graph, such that no adjacent vertices have the same color. The number of colors used corresponds to the number of parallel steps in a real-world end-application. Therefore, the total runtime of the graph coloring kernel adds to the overall parallel overhead of the real-world end-application, whereas the number of the vertices of each color class determines the number of the independent concurrent tasks of each parallel step, thus affecting the amount of parallelism and hardware resource utilization in the execution of the real-world end-application. In this work, we propose a high-performance graph coloring algorithm, named ColorTM, that leverages Hardware Transactional Memory (HTM) to detect coloring inconsistencies between adjacent vertices. ColorTM detects and resolves coloring inconsistencies between adjacent vertices with an eager approach to minimize data access costs, and implements a speculative synchronization scheme to minimize synchronization costs and increase parallelism. We extend our proposed algorithmic design to propose a balanced graph coloring algorithm, named BalColorTM, with which all color classes include almost the same number of vertices to achieve high parallelism and resource utilization in the execution of the real-world end-applications. We evaluate ColorTM and BalColorTM using a wide variety of large real-world graphs with diverse characteristics. ColorTM and BalColorTM improve performance by 12.98 × and 1.78 × on average using 56 parallel threads compared to prior state-of-the-art approaches. Moreover, we study the impact of our proposed graph coloring algorithmic designs on a popular end-application, i.e., Community Detection, and demonstrate the ColorTM and BalColorTM can provide high-performance improvements in real-world end-applications across various input data given.

DP-coloring (also known as correspondence coloring) is a generalization of list coloring introduced recently by Dvořák and Postle [12]. Many known upper bounds for the list-chromatic number extend to the DP-chromatic number, but not all of them do. In this note we describe some properties of DP-coloring that set it aside from list coloring. In particular, we give an example of a planar bipartite graph with DP-chromatic number 4 and prove that the edge-DP-chromatic number of a d -regular graph with d ⩾ 2 is always at least d + 1.

The vertex graph coloring problem (VGCP) is one of the most well-known problems in graph theory. It is used for solving several real-world problems such as compiler optimization, map coloring, and frequency assignment. The goal of VGCP is to color all vertices of the graph so that adjacent vertices receive different colors and the number of different colors used is minimized. The main difficulty of this problem resides when the graph size increases, that induces the increase in complexity of the VGCP which gives it the characteristic of being an NP-hard problem. To deal with this problem in the context of large graphs, different options are considered, including new large graph parallel processing frameworks such as Pregel, Graphx and Giraph. The latter is viewed as one of the most popular large graph processing frameworks both in industry and academia. In this work, we propose a new parallel graph coloring algorithm, called DistG, based on the vertex-centric computation model. The main feature of the proposed algorithm is that it colors all the vertices in its second superstep, corresponding to the initial coloration stage, and in the other supersteps takes care of conflict correction. And this allows it to exclude from the computation from the third superstep all the vertices not concerned by conflicts, what makes it several important gains in terms of number of supersteps, number of exchanged messages, and execution time. For its implementation, we have used the Giraph framework but it can be easily adaptable to any vertex-centric system. We have evaluated the DistG algorithm on several datasets from the SNAP graph benchmark using a Hadoop Cluster. The obtained results have shown that the proposed algorithm performs better than concurrent algorithms in terms of number of colors, CPU time, number of supersteps, and communication cost.

The Vertex Graph Coloring problem ( VGC ) is a well-known difficult combinatorial optimization problem. It is one of Karp’s 21 NP-complete problems. It consists in assigning a color to each vertex of a graph in such a way that any two neighboring vertices do not share the same color, and the number of the used colors is minimized. VGC is used to solve a variety of real-world problems such as time tabling and scheduling, radio frequency assignment, and computer register allocation. To deal with this problem on large graphs, the emerging large graph processing frameworks are an excellent promising candidate. Giraph is one of the most popular large graph processing frameworks both in industry and academia. In this work, two novel graph coloring algorithms are introduced. These algorithms designed to reap the benefit of the simple parallelization model offered by any vertex-centric frameworks, such as Giraph. The algorithms are based on well-known sequential heuristic techniques namely Largest-First (LF) and Saturation Largest-First (SLF). We have compared the performances of the proposed algorithms to previous Giraph based graph coloring algorithms, with regard to their solution quality and executing time, using benchmark graphs from the SNAP library. The obtained experimental results have revealed that the proposed algorithms are much more efficient than the existing Giraph algorithms.

The vague graph has found its importance as a closer approximation to real life situations. A review of the literature in this area reveals that the edge coloring problem for vague graphs has not been studied until now. Therefore, in this paper, we analyse the concept of vertex and edge coloring on simple vague graphs. Specifically, two new definitions for vague graphs related to the concept of the λ-strong-adjacent and ζ-strong-incident of vague graphs are introduced. We consider the color classes to analyze the coloring on the vertices in vague graphs. The proposed method illustrates the concept of coloring on vague graphs, using the definition of color class, which depends only on the truth membership function. Applications of the proposal in solving practical problems related to traffic flow management and the selection of advertisement spots are mainly discussed.

In this article, we consider the NP-hard problem of the two-step coloring of a graph. It is required to color the graph in the given number of colors in a way, when no pair of vertices has the same color, if these vertices are at a distance of one or two between each other. The optimum two-step coloring is one that uses the minimum possible number of colors. The two-step coloring problem is studied in application to grid graphs. We consider four types of grids: triangular, square, hexagonal, and octagonal. We show that the optimum two-step coloring of hexagonal and octagonal grid graphs requires four colors in the general case. We formulate the polynomial algorithms for such a coloring. A square grid graph with the maximum vertex degree equal to 3 requires four or five colors for a two-step coloring. In this paper, we propose the backtracking algorithm for this case. Also, we present the algorithm, which works in linear time relative to the number of vertices, for the two-step coloring in seven colors of a triangular grid graph and show that this coloring is always correct. If the maximum vertex degree equals six, the solution is optimum.

The graph coloring problem is an NP-hard problem. Currently, one of the most effective methods to solve this problem is a hybrid evolutionary algorithm. This paper proposes a hybrid evolutionary algorithm NERS_HEAD with a new elite replacement strategy. In NERS_HEAD, a method to detect the local optimal state is proposed so that the evolutionary process can jump out of the local optimal state by introducing diversity on time; a new elite structure and a replacement strategy are designed to increase the diversity of the evolutionary population so that the evolution process can not only converge quickly but also jump out of the local optimal state in time. The comparison experiments with current excellent graph coloring algorithms on 59 DIMACS benchmark instances show that NERS_HEAD can effectively improve the efficiency and success rate of solving graph coloring problems.

Semidefinite programs (SDPs) can be solved in polynomial time by interior point methods. However, when the dimension of the problem gets large, interior point methods become impractical in terms of both computational time and memory requirements. Certain first-order methods, such as Alternating Direction Methods of Multipliers (ADMMs), established as suitable algorithms to deal with large-scale SDPs and gained growing attention over the past decade. In this paper, we focus on an ADMM designed for SDPs in standard form and extend it to deal with inequalities when solving SDPs in general form. Beside numerical results on randomly generated instances, where we show that our method compares favorably with respect to the state-of-the-art solver  SDPNAL+ (Yang et al. in Math Program Comput 7:331–366, 2015), we present results on instances from SDP relaxations of classical combinatorial problems such as the graph coloring problem and the maximum clique problem. Through extensive numerical experiments, we show that even an inaccurate dual solution, obtained at a generic iteration of our proposed ADMM, can represent an efficiently recovered valid bound on the optimal solution of the combinatorial problems considered, as long as an appropriate post-processing procedure is applied.