REDUCING COMPUTATIONAL OVERHEAD IN NETWORK GRAPH PARTITIONING

Authors

Srinivasa Reddy Kummetha

Abstract

A graph is a conceptual framework consisting of a set of points, commonly called nodes or vertices, interconnected by lines, referred to as edges or links. Each edge serves as a bridge between two vertices, signifying an association or interaction between them. Graphs can be classified based on the nature of their vertices and edges. A directed graph, or digraph, features edges with a specific orientation, indicating movement from one vertex to another. Conversely, an undirected graph lacks directional edges, implying a mutual connection between linked vertices. In a weighted graph, edges are assigned numerical values, typically representing factors such as distance, expense, or capacity, whereas unweighted graphs solely depict connectivity without additional numerical attributes. Graph coloring is a strategy where distinct identifiers, often represented as colors, are assigned to vertices or edges under specific constraints. The fundamental goal of this approach is to ensure that adjacent elements do not share the same identifier. This technique is widely applied to practical problems, including resource allocation, conflict resolution, and organizational planning. For instance, it is used in designing schedules where overlapping assignments must be avoided, frequency allocation in wireless networks to minimize interference, and even in solving logic puzzles like Sudoku. The chromatic number of a graph represents the least number of colors required to achieve a valid coloring. Depending on its structure, a graph might require only two colors (rendering it bipartite) or more. A commonly used method for graph coloring is the greedy algorithm, which assigns colors sequentially by selecting the smallest available color that has not yet been used for neighboring vertices. While this approach provides a straightforward and fast solution, it does not always yield the minimum number of colors required. Finding the most efficient coloring scheme, known as the minimum chromatic number, is a computationally complex problem categorized as NP-complete, meaning it becomes increasingly challenging for larger graphs. Despite this difficulty, graph coloring has significant applications in numerous domains. In programming, it helps with register allocation in compilers to optimize CPU efficiency. In telecommunications, it aids in preventing signal interference by assigning appropriate frequencies. Additionally, it plays a crucial role in logistics, ensuring that tasks and resources are scheduled efficiently without conflicts. This paper addresses the huge time complexity issue while resolving 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.

REDUCING COMPUTATIONAL OVERHEAD IN NETWORK GRAPH PARTITIONING. Srinivasa Reddy Kummetha. 2020. IJIRCT, Volume 6, Issue 5. Pages 1-21. https://www.ijirct.org/viewPaper.php?paperId=2504033