Degree-Based Logical Adjacency Checking (DBLAC): A Novel Heuristic for Vertex Coloring
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915114175692800 |
|---|---|
| author | Verma, Prashant |
| author_facet | Verma, Prashant |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_12479 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Degree-Based Logical Adjacency Checking (DBLAC): A Novel Heuristic for Vertex Coloring Verma, Prashant Discrete Mathematics Artificial Intelligence 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. |
| title | Degree-Based Logical Adjacency Checking (DBLAC): A Novel Heuristic for Vertex Coloring |
| topic | Discrete Mathematics Artificial Intelligence |
| url | https://arxiv.org/abs/2501.12479 |