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
, DE
and CF
can be tested in parallel in the first cycle, followed AD
, BC
and EF
during the second. This leaves only BE
for 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 CF
can be visited first, and then BC
and AD
. this leaves BE
, DE
and EF
for testing one at a time in 5 cycles. This is less efficient than the first AB
, and DE
, then BC
, and EF
in seconds, AD
and BE
in 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.
source
share