The Graph Coloring Problem (GCP) is assigning different colors to certain elements in a graph based on certain constraints and using a minimum number of colors. GCP can be drawn into optimization ...problems, namely the problem of minimizing the color used together with the uncertainty in using the color used, so it can be assumed that there is an uncertainty in the number of colored vertices. One of the mathematical optimization techniques in dealing with uncertainty is Robust Optimization (RO) combined with computational tools. This article describes a robust GCP using the Polyhedral Uncertainty Theorem and model validation for electrical circuit problems. The form of an electrical circuit color chart consists of corners (components) and edges (wires or conductors). The results obtained are up to 3 colors for the optimization model for graph coloring problems and up to 5 colors for robust optimization models for graph coloring problems. The results obtained with robust optimization show more colors because the results contain uncertainty. When RO GCP is applied to an electrical circuit, the model is used to place the electrical components in the correct path so that the electrical components do not collide with each other.
The graph coloring problem (GCP) is a fundamental combinatorial optimization problem that has many practical applications. Degree of SATURation (DSATUR) and Recursive Largest First (RLF) are well ...known as typical solution construction algorithms for GCP. It is necessary to update the vertex degree in the subgraph induced by uncolored vertices when selecting vertices to be colored in both DSATUR and RLF. There is an issue that the higher the edge density of a given graph, the longer the processing time. The purposes of this paper are to propose a degree updating method called Adaptive Degree Updating (ADU for short) that improves the issue and to evaluate the effectiveness of ADU for DSATUR and RLF on DIMACS benchmark graphs as well as random graphs having a wide range of sizes and densities. Experimental results show that the construction algorithms with ADU are faster than the conventional algorithms for many graphs and the ADU method yields significant speed-ups relative to the conventional algorithms, especially in the case of large graphs with higher edge density.
Graph Coloring Problem (GCP) is the assignment of colors to certain elements in a graph based on certain constraints. GCP is used by assigning a color label to each node with neighboring nodes ...assigned a different color and the minimum number of colors used. Based on this, GCP can be drawn into an optimization problem that is to minimize the colors used. Optimization problems in graph coloring can occur due to uncertainty in the use of colors to be used, so it can be assumed that there is an uncertainty in the number of colored vertices. One of the mathematical optimization methods in the presence of uncertainty is Robust Optimization (RO). RO is a modeling methodology combined with computational tools to process optimization problems with uncertain data and only some data for which certainty is known. This paper will review research on Robust GCP with model validation to be applied to electrical circuit problems using a systematic review of the literature. A systematic literature review was carried out using the Preferred Reporting Items for Systematic reviews and Meta Analysis (PRISMA) method. The keywords used in this study were used to search for articles related to this research using a database. Based on the results of the search for articles obtained from PRISMA and Bibliometric R Software, it was found that there was a relationship between the keywords Robust Optimization and Graph Coloring, this means that at least there is at least one researcher who has studied the problem. However, the Electricity keyword has no relation to the other two keywords, so that a gap is obtained and it is possible if the research has not been studied and discussed by other researchers. Based on the results of this study, it is hoped that it can be used as a consideration and a better solution to solve optimization problems.
A multicell massive multiple-input multiple-output (MIMO) system, which utilizes a large number of base-station antennas to simultaneously serve a set of users, suffers from pilot contamination (PC) ...due to unavoidable reuse of pilots in adjacent cells. In this paper, a weighted-graph-coloring-based pilot decontamination (WGC-PD) scheme is proposed to mitigate PC for multicell massive MIMO systems. Specifically, based on limited cooperation among cells, an edge-weighted interference graph (EWIG) is first constructed to depict the potential PC relationship among users, whereby two users in different cells are connected by a weighted edge, indicating the strength of potential PC when they reuse the same pilot. Then, inspired by classical graph coloring algorithms, we develop the WGC-PD scheme by denoting each color as a pilot and each vertex as a user in the EWIG, which is able to mitigate PC by assigning different pilots to connected users with a large weight in a greedy way with insufficient pilot resource. Compared with exhaustive search among numerous pilot assignment solutions, the proposed WGC-PD scheme is able to mitigate PC with significantly reduced complexity, which is verified by numerical results.
•Novel discrete approach for combinational optimization based on cuckoo optimization algorithm (COA).•Redefining the difference concept between two habitats as a differential list of ...movements.•Proposed method enable to solve non-permutation problems.•Modifying egg laying and immigration phase of COA in the proposed discrete cuckoo optimization algorithm (DCOA).•High quality results obtained for graph coloring problems.
In recent years, various heuristic optimization methods have been developed. Many of these methods are inspired by swarm behaviors in nature, such as particle swarm optimization (PSO), firefly algorithm (FA) and cuckoo optimization algorithm (COA). Recently introduced COA, has proven its excellent capabilities, such as faster convergence and better global minimum achievement. In this paper a new approach for solving graph coloring problem based on COA was presented. Since COA at first was presented for solving continuous optimization problems, in this paper we use the COA for the graph coloring problem, we need a discrete COA. Hence, to apply COA to discrete search space, the standard arithmetic operators such as addition, subtraction and multiplication existent in COA migration operator based on the distance's theory needs to be redefined in the discrete space. Redefinition of the concept of the difference between the two habitats as the list of differential movements, COA is equipped with a means of solving the discrete nature of the non-permutation. A set of graph coloring benchmark problems are solved and its performance is compared with some well-known heuristic search methods. The obtained results confirm the high performance of the proposed method.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
Context-sensitive fusion grammars and fusion grammars with forbidden context are special cases of context-dependent fusion grammars where instead of finite sets of positive and negative context ...conditions in the first case a rule has only a single positive context condition and in the second case a rule has only a finite set of negative context conditions. In this paper, we show that several decision problems can be formulated quite intuitively by these grammars. In particular, we show that the Boolean satisfiability problem as well as the Post correspondence problem can be transformed into a context-sensitive fusion grammar and that the graph coloring problem can be transformed into a fusion grammar with forbidden context such that the generated languages give solutions for the problems. Furthermore, we prove that both grammar types can generate all recursively enumerable string languages (up to representation of strings as graphs) and are universal in this respect.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
8.
Ising-Machine-Based Solver for Constrained Graph Coloring Problems KAWAKAMI, Soma; MUKASA, Yosuke; BAO, Siya ...
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,
2024/01/01, 2024-1-1, 20240101, Volume:
E107.A, Issue:
1
Journal Article
Peer reviewed
Open access
Ising machines can find optimum or quasi-optimum solutions of combinatorial optimization problems efficiently and effectively. The graph coloring problem, which is one of the difficult combinatorial ...optimization problems, is to assign a color to each vertex of a graph such that no two vertices connected by an edge have the same color. Although methods to map the graph coloring problem onto the Ising model or quadratic unconstrained binary optimization (QUBO) model are proposed, none of them considers minimizing the number of colors. In addition, there is no Ising-machine-based method considering additional constraints in order to apply to practical problems. In this paper, we propose a mapping method of the graph coloring problem including minimizing the number of colors and additional constraints to the QUBO model. As well as the constraint terms for the graph coloring problem, we firstly propose an objective function term that can minimize the number of colors so that the number of used spins cannot increase exponentially. Secondly, we propose two additional constraint terms: One is that specific vertices have to be colored with specified colors; The other is that specific colors cannot be used more than the number of times given in advance. We theoretically prove that, if the energy of the proposed QUBO mapping is minimized, all the constraints are satisfied and the objective function is minimized. The result of the experiment using an Ising machine showed that the proposed method reduces the number of used colors by up to 75.1% on average compared to the existing baseline method when additional constraints are not considered. Considering the additional constraints, the proposed method can effectively find feasible solutions satisfying all the constraints.
The minimum load coloring problem consists of finding a 2-coloring function that assign either a color red or blue to each node of a graph such that the (maximum) load is minimized, i.e., to reduce ...as much as possible the number of edges with, at least, one endpoint colored in red (symmetrically, in blue). This
NP
-complete problem arises in Wavelength Division Multiplexing (WDM) technology and it has been used for broadcast WDM networks. In this paper, several procedures based on the Variable Neighborhood Search (VNS) methodology are proposed and compared on a set of random graphs and DIMACS benchmarks. Experimental results show that the proposed VNS variant exhibits a remarkable performance in comparison with the state-of-the-art methods. In particular, our approach achieves the best results in 48 out of 52 considered instances by employing, on average, less than 7 seconds. These results are further confirmed by conducting statistical tests.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
The Graph Coloring Problem (GCP) is a fundamental combinatorial optimization problem that has many practical applications. Degree of SATURation (DSATUR) and Recursive Largest First (RLF) are well ...known as typical solution construction algorithms for GCP. It is necessary to update the vertex degree in the subgraph induced by uncolored vertices when selecting vertices to be colored in both DSATUR and RLF. There is an issue that the higher the edge density of a given graph, the longer the processing time. The purposes of this paper are to propose a degree updating method called Adaptive Degree Updating (ADU for short) that improves the issue, and to evaluate the effectiveness of ADU for DSATUR and RLF on DIMACS benchmark graphs as well as random graphs having a wide range of sizes and densities. Experimental results show that the construction algorithms with ADU are faster than the conventional algorithms for many graphs and that the ADU method yields significant speed-ups relative to the conventional algorithms, especially in the case of large graphs with higher edge density.
