JONES-PLASSMANN ALGORITHM FOR ADAPTIVE NETWORK CONFLICT RESOLUTION

Authors: Raghavendra Prasad Yelisetty

Country: United States

Full-text Research PDF File:   View   |   Download

Abstract: A graph is a mathematical model composed of a collection of vertices (or nodes) connected by edges (or links). Each edge links two vertices, symbolizing a relationship or connection between them. Graphs can be categorized into different types based on the characteristics of their edges and vertices. A directed graph (digraph) has edges with a direction, meaning the edges point from one vertex to another. On the other hand, an undirected graph consists of edges that have no specific direction, indicating that the connection between the two vertices is bidirectional. In a weighted graph, each edge is assigned a numerical value or weight, which is often used to represent measurements like distance, cost, or capacity, whereas in an unweighted graph, edges merely show a connection without any associated numerical value. Graph coloring is a technique where colors are applied to vertices (or edges) under certain constraints. The main objective of graph coloring is to ensure that no two adjacent vertices (or edges) share the same color. This method is crucial in solving various real-world challenges such as task scheduling, coloring regions on maps, assigning frequencies in communication systems, and even in puzzle solving like Sudoku. A valid coloring ensures that no two adjacent vertices share the same color. The chromatic number of a graph is the minimum number of colors required to color the graph properly. For instance, a graph may need two colors (making it bipartite) or more, depending on its structure. The greedy coloring algorithm is one of the simplest techniques for coloring a graph. It colors each vertex sequentially, choosing the smallest color that hasn’t been assigned to adjacent vertices. However, this method does not always guarantee the minimum chromatic number but offers a quick and easy solution. Finding the optimal coloring, or the minimum number of colors needed, is generally difficult and considered an NP-complete problem, meaning finding the exact solution can be computationally demanding for large graphs. Despite its complexity, graph coloring has many practical uses. For example, in compiler construction, it is used for efficiently allocating registers in a CPU. In network design, graph coloring is applied to frequency assignments to prevent interference. It is also used in scheduling problems where resources must be allocated at specific times without overlap. This paper addresses the huge memory usage while resolving the conflicts using the Hybrid Graph Partitioning.

Keywords: Graph, Node, Connection, Directed Graph, Undirected Graph, Weighted Graph, Unweighted Graph, Bipartite Graph, Tree, Subgraph, Isomorphism, Chromatic Value, Graph Coloring.

Paper Id: 232348

Published On: 2021-08-12

Published In: Volume 9, Issue 4, July-August 2021

Share this