Degree-Based Logical Adjacency Checking (DBLAC): A Novel Heuristic for Vertex Coloring
Degree Based Logical Adjacency Checking (DBLAC). An efficient coloring of graphs with unique logical AND operations. The logical AND operation shows more effective color assignment and fewer number of induced colors in the case of common edges between vertices. In this work, we provide a detailed theoretical analysis of DBLAC's time and space complexity. It furthermore shows its effectiveness through prolonged experiments on standard benchmark graphs. We compare it with existing algorithms, namely DSATUR and Recursive Largest First (RLF). Second, we show how DBLAC achieves competitive results with respect to both the number of colors used and runtime performance.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
What constrains food webs? A maximum entropy framework for predicting their structure with minimal biases
Food webs are complex ecological networks whose structure is both ecologically and statistically constrained, with many network properties being correlated with each other. Despite the recognition of these invariable rel…
Heuristics based on Adjacency Graph Packing for DCJ Distance Considering Intergenic Regions
In this work, we explore heuristics for the Adjacency Graph Packing problem, which can be applied to the Double Cut and Join (DCJ) Distance Problem. The DCJ is a rearrangement operation and the distance problem consideri…
Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction
Graph Neural Networks (GNNs) have been widely applied to various fields for learning over graph-structured data. They have shown significant improvements over traditional heuristic methods in various tasks such as node c…
Graph ClassificationLink PredictionNode ClassificationPredictionTransformers Provably Learn Algorithmic Solutions for Graph Connectivity, But Only with the Right Data
Transformers often fail to learn generalizable algorithms, instead relying on brittle heuristics. Using graph connectivity as a testbed, we explain this phenomenon both theoretically and empirically. We consider a simpli…
Link Discovery using Graph Feature Tracking
We consider the problem of discovering links of an evolving undirected graph given a series of past snapshots of that graph. The graph is observed through the time sequence of its adjacency matrix and only the presence o…
Matrix Completion