Harmonious Coloring: Greedy & Suboptimal Algos

  • Thread starter Thread starter bob j
  • Start date Start date
AI Thread Summary
A greedy algorithm for harmonious coloring on a graph involves starting with a connected graph where only one node is initially colored. The algorithm maintains a list of used color pairs and colors adjacent nodes by reusing existing colors when possible, or introducing new colors as needed. This process continues until all nodes are colored. The approach is straightforward and effectively utilizes existing colors to minimize the introduction of new ones. Such algorithms can provide quick, albeit suboptimal, solutions for harmonious coloring problems.
bob j
Messages
22
Reaction score
0
Hi All,
does anyone know of any greedy or suboptimal algorithm to obtain harmonious coloring on a graph?
 
Mathematics news on Phys.org
what exactly do u want to use it for?
 
Sure, you could easily imagine a greedy suboptimal algorithm. Start with a connected graph where all nodes are colorless but one, which has color 1. Maintain a list of color pairs that have already been used. At every step, color a node which is adjacent to a previous node, using an existing color if possible, otherwise using a new color. Continue until all nodes are colored.
 

Thread 'Non-orthogonal bases'

Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
View full post »

Thread 'What Exactly is Dirac’s Delta Function? - Insight'

Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
View full post »

Similar threads

Use greedy vertex coloring algorithm to prove the upper bound of χ
Replies
0
Views
95
I Find Smallest Subtree of G w/ Nodes from S
Replies
5
Views
2K
I Finding the dependence of maximum vertex degree on k-colorability
Replies
1
Views
1K
MHB Optimizing Wireless Internet Coverage for Houses: A Greedy Algorithm Approach
Replies
3
Views
2K
I Traffic simulation : directed graph including specific rules
Replies
5
Views
2K
I Video on imaginary numbers and some queries
Replies
2
Views
1K
Greedy Algorithm & Optimal Coin Change
Replies
3
Views
5K
B Understanding Horner's Method: A Brief Explanation for Confusion
Replies
7
Views
2K
Some questions about Fourier transformation
Replies
13
Views
2K
Can Greedy Coloring on Chordal Graph Complements Be Proven Optimal?
Replies
1
Views
3K

Hot Threads

Recent Insights

Back
Top