62 results about "Graph coloring" patented technology

An improved method is provided for performing register allocation in a compiler. This method determines the allocation of a plurality R of registers of a processor for use during the execution of a software program. The register allocation process is treated as a graph-coloring problem, such that an interference graph is constructed for the software program, the graph is simplified, and an R-coloring the interference graph to the extent possible is attempted. Then, spill code is inserted in the software program each for each uncolored node of the graph, a new interference graph is constructed, and the process is repeated. During the simplification process, nodes with degree greater than or equal to R are removed from the graph in an order dictated by a spill cost metric. During the coloring process, these same nodes are reinserted in the graph in an order dictated by reapplying the spill cost metric.

The invention discloses a frequency domain resource distribution method based on graph coloring in an ultra-dense network. The frequency domain resource distribution method comprises the following steps: reflecting a disturbed condition between small stations by utilizing a disturbance relationship graph; and coloring the disturbance relationship graph by utilizing a multiplexing algorithm based on a conventional graph coloring Brelaz algorithm, and distributing sub-band for each user according to the coloring results, thereby achieving a purpose of reducing the disturbance between the small stations. The method disclosed by the invention can be used for remarkably reducing the disturbance between the small stations, so that the total throughput and edge throughput of the system are increased.

The invention discloses a method for discovering small stations based on graph coloring in an ultra-dense wireless network. The method comprises the steps that the number of small station groups, namely the available color number Ncolors, is determined by an operator; a multiplex distance dreuse which is as big as possible is found under the premise that the used color number is not larger than the Ncolors; an interference relation graph is established according to the dreuse, and a Brelaz algorithm is used for coloring; the small stations are grouped according to coloring results, and all groups of small stations are made to send synchronous signals in turn; when network topology changes, the interference relation graph is reestablished, coloring is conducted again, the small stations are regrouped, and the small stations are made to send synchronous signals in turn according to the new groups. According to the method, the small stations are grouped, the interference of the synchronous signals of different small stations is reduced; the interference relations between the small stations are reflected through the interference relation graph, so that the small stations which interfere with each other seriously are prevented from being distributed in the same group, and the interference between the small stations is further reduced; the probability that UE discovers weak small stations is improved, and the number of the small stations discovered by the UE is increased.

The invention relates to a graph coloring node operation method based on the ring-shaped DNA, comprising the following steps of obtaining the coloring scheme congregation of a vertex corresponding to a graph according to given color kinds; finding out two edges with undetermined vertex colors from edges with nonadjacent but connected vertex digit sequences according to the coloring scheme congregation of the vertex; and deleting and untying the two edges with undetermined vertex colors by the operation of the ring-shaped DNA and a backtracking method to obtain the true solution set of vertex coloring schemes. The technical proposal of the invention is to explain graphs, avoids the molecule recombination by concurrency of the life-form operation of the DNA operation and based on the characteristic of the operation of the ring-shaped DNA, and gradually obtains the vertex coloring scheme congregation for a coloring graph, thereby organically combining an optimized operation method, DNA sequence codes, various biochemistry operations, solution detection problems, solution space scales and the like, and enhancing the solving rate of the coloring problem of a graph.

The invention discloses a method for allocating registers for a mixed length instruction set. By less revising the conventional graph coloring register allocation method, namely fully utilizing the characteristics of a mixed coding instruction set, codes with higher code density are generated. The method has the characteristics of simplicity, practicability and high in reliability.

The invention discloses a D2D resource allocation method based on graph coloring. The method comprises the steps of assuming that all D2D users in a system multiplex channel resources of the same cellular user and take threshold power as transmitting power; obtaining an unignorable undirected mutual interference graph, wherein the interference value is the weight of each edge of the graph; dividing all D2D users in a cell into a plurality of clusters with relatively low mutual interference degrees through a graph coloring method; the users with the same color are the same cluster; enabling theD2D users in each cluster to multiplex the same cellular channel, acquiring a cellular channel capable of being multiplexed by each cluster, calculating the maximum throughput for matching all the cellular channels with the D2D clusters in pairs one by one, setting the throughput of the D2D clusters and the cellular channels which cannot be matched to be zero, and acquiring a throughput matrix; and solving an optimal matching matrix for maximizing the system throughput, allocating channel resources to the D2D cluster according to the matching matrix, and taking a power solution obtained by using a Lagrangian multiplier method as the transmitting power of the D2D pair.

The invention discloses a frequency spectrum polymerization method assisted by time division long term evolution (TD-LTE) Femtocell database using TV White Space (TVWS). In order to achieve the frequency spectrum polymerization method, the invention further provides a centralized control entity compatible with a database structure suggested by the federal communications commission (FCC) and a modeling approach considering graph coloring model in the process of frequency spectrum polymerization. The frequency spectrum polymerization method takes full advantage of uneven cochannel interference relationship between family base stations (FBSs). Database-assisted Spectrum Aggregation Algorithm (DSAA) is applied to the graph coloring model in the process of considering frequency spectrum polymerization, and therefore the Femtocell is enabled to obtain good system access performance on aspects of general system access bandwidth and the number of the FBSs system access.

A system, method, and computer program product are provided for performing graph coloring. In use, a graph with a plurality of vertices is identified. Additionally, the plurality of vertices of the graph is categorized, where the categorizing of the plurality of vertices is optimized.

The invention provides a GPU-based dynamic graph coloring method. The method comprises the following steps: converting an original undirected graph into a directional graph; updating directional diagrams after multiple deletion and inserting operation is carried out in batches; storing outer adjacent information of the directional diagram in a compressed sparse row CSR mode, storing inner adjacent information of the directional diagram in a compressed sparse column CSC mode, and transmitting the outer adjacent information and the inner adjacent information to a GPU global memory; judging whether the queue is empty or lower than a threshold value, if not, partitioning a subgraph formed by the to-be-updated node by using a greedy coloring method, and transmitting a partitioning result to the GPU; if yes, processing by the CPU end; carrying out parallel RC-processing of nodes in each region according to partitioning results Hybrid coloring. According to the method, the parallel processing capability of the GPU can be fully utilized, hybrid partitioning design is carried out on the nodes to be processed, the concurrency is improved, and the correctness and the consistency of a coloring result are ensured.

The invention provides a spectrum management method and system based on a smart grid double-layer cognitive network architecture. The method comprises the following steps: receiving a spectrum conversion request, performing spectrum allocation between power information terminals in the smart grid double-layer cognitive network architecture by using a graph coloring part of an interference reduction type graph coloring-simulated annealing fusion algorithm, obtaining real-time spectrum information, establishing an available spectrum matrix and an inter-cell spectrum interference matrix, establishing a local solution list, calculating the optimum spectrum allocation through a simulated annealing part of the interference reduction type graph coloring-simulated annealing fusion algorithm according to the established local solution list and the inter-cell spectrum interference matrix, and feeding back an optimum spectrum allocation result to the power information terminals. During the entire process, by taking the interference reduction type graph coloring-simulated annealing fusion algorithm as a spectrum management allocation core, an optimum spectrum allocation strategy of a smart grid double-layer network can be quickly acquired, and spectrum resources in the network can be fully used.

The invention discloses a hybrid heuristic graph coloring method, which integrates a probability learning strategy and a hybrid evolution algorithm, and performs hybrid evolution based on two coloring grouping schemes. And before hybrid purification, according to a conditional grouping strategy, a probability learning strategy is introduced according to a coloring distribution similarity degree of two coloring grouping schemes to carry out coloring dynamic adjustment, so that better balance exists between rapid convergence and population diversity maintenance, and while the relatively high solving efficiency of the image coloring grouping scheme is maintained, the image quality is improved. And the resolving precision is further improved, so that the resolving precision and the resolving efficiency of the graph coloring problem are better balanced and considered.

The invention discloses a method for drawing a benefit map of every ten thousand yuan of power sale quantity of a power grid asset unit. According to the method, through combination of scientific classification of the asset unit, data map series layers of the asset unit are established; and evaluation index values are assigned for "every ten thousand yuan of asset power sale quantity" of different apertures of asset units, the evaluation index grades are classified and graph coloring definition is performed on different grades of evaluation index, and the layers of different apertures of asset units are colored separately, so that benefit maps of "every ten thousand yuan of asset power sale quantity" of different apertures of asset units are obtained. The method is convenient and scientific.

The invention relates to a D2D communication resource allocation method for improving graph coloring, and the method comprises the following steps: S1, calculating the signal-to-interference-and-noiseratio of cellular users and D2D users; S2, calculating a safety distance di between D2D users; S3, determining a D2D user set of which the D2D users can share the same channel; S4, constructing a D2Duser multiplexing relation graph; S5, grouping the D2D users according to an improved graph coloring principle in combination with accumulated interference among the D2D users; and S6, allocating channel resources to each multiplexing group by using a Hungary algorithm; According to the method, the throughput of the cellular system and the access rate of the D2D users are improved, the resource utilization rate is effectively optimized, the interference between the D2D users can be reduced, and the service quality of D2D communication is ensured.

The invention relates to an anti-collision graph coloring two-stage distribution method for an RFID reader. The method comprises two stages of graph coloring distribution schemes which are sequentially executed in each round and are respectively a graph coloring first-stage distribution scheme and a graph coloring second-stage distribution scheme. The first-stage graph coloring allocation scheme relates to a color time slot initialization stage and a time slot resource competition and back-off judgment stage, and the second-stage graph coloring allocation scheme relates to an estimation and reallocation stage of idle time slots; according to the method, the anti-collision problem of the RFID reader is converted into the coloring optimization problem of the RFID reader; through mutual coordination and communication, the RFID readers which collide with each other can negotiate the allocation of time slot resources friendly, and the secondary collision of the RFID readers is reduced. theRFID reader estimates available idle time slots according to the distribution of the neighbor RFID readers, and more time slot resources are obtained in a competitive manner, so that the efficient utilization of the time slot resources is realized, and the throughput rate and the label identification rate of the RFID reader network are maximized.