Paper Details
ELEVATING BEST-CASE COMPLEXITY PERFORMANCE IN CONTEXT-FREE GRAPH COLORING USING LUBY’S ALGORITHM
Authors
Raghavendra Prasad Yelisetty
Abstract
A graph serves as a structured representation consisting of a set of points, known as vertices or nodes, that are linked by connecting elements referred to as edges or arcs. Each edge forms a linkage between two vertices, signifying a relationship or interaction between them. Graphs can be classified into various categories based on their structural properties. A directed graph, often called a digraph, contains edges with specific orientations, indicating movement from one vertex to another, whereas an undirected graph features bidirectional edges, implying a mutual association between the connected vertices. In weighted graphs, edges carry numerical values representing factors like cost, distance, or capacity, whereas unweighted graphs simply indicate connectivity without additional metrics. Graph coloring is a method where unique markers, commonly referred to as colors, are assigned to vertices or edges while adhering to specific rules. The chromatic number of a graph represents the smallest number of distinct colors required for a valid coloring schemeWhile this method offers a straightforward and fast solution, it does not always guarantee the minimum number of required colors. Determining the most efficient coloring scheme, known as the minimal chromatic number, is an NP-complete problem, meaning that it becomes computationally challenging as graph size increases. Despite its complexity, graph coloring is widely applied across numerous domains. In computing, it is used for register allocation in compilers to enhance CPU efficiency. In telecommunications, it ensures optimal frequency allocation to prevent signal interference. Additionally, it plays a critical role in logistics by ensuring that resources and tasks are efficiently scheduled without conflicts. This paper addresses on optimizing best case complexity of context free graph coloring using lubys algorithm.
Keywords
Graph, Node, Connection, Directed Graph, Undirected Graph, Weighted Graph, Unweighted Graph, Bipartite Graph, Tree, Subgraph, Isomorphism, Chromatic Value, Graph Coloring.
Citation
ELEVATING BEST-CASE COMPLEXITY PERFORMANCE IN CONTEXT-FREE GRAPH COLORING USING LUBY’S ALGORITHM. Raghavendra Prasad Yelisetty. 2023. IJIRCT, Volume 9, Issue 1. Pages 1-18. https://www.ijirct.org/viewPaper.php?paperId=2504030