Algorithm for parallel processing of graph boundaries?

Question

Link Chart:

I am writing a program that checks all edges of a graph. A program can check graph boundaries in parallel if and only if they do not have a common node. My problem is that I should also be able to not check the edges in the most efficient way.

If you check the most effective choice of parallel ribs on the above graph, Edges AB, DEand CFcan be tested in parallel in the first cycle, followed AD, BCand EFduring the second. This leaves only BEfor the third cycle.

If I restrict myself to only two parallel ribs at once, I could then visit the edges in several ways, some more effective than others. For example AB, and CFcan be visited first, and then BCand AD. this leaves BE, DEand EFfor testing one at a time in 5 cycles. This is less efficient than the first AB, and DE, then BC, and EFin seconds, ADand BEin the third, and CF- as the final edge for a total of 4 cycles.

Is there an algorithm or practice that can be applied to find the most effective way to visit the chart this way? My graphs are of variable size and connectivity, so I can’t personally decide and plan them, even if I wanted to.

Any help or direction would be appreciated. It has been some time since there was a lesson in graph theory, so I don’t remember if any of this character exists. I am currently theoretically approaching this problem and have not yet begun trying to implement any programs on this aspect. Thus, if my question is better directed elsewhere, I would be more than happy to move my question to the appropriate Stack Exchange site.

Answer 1

This issue is red coloring: https://en.wikipedia.org/wiki/Edge_coloring

If you color the edges of the graph so that two adjacent edges do not have the same color, you can do one cycle for each color, checking all the edges of that color in parallel.

, NP-.