An efficient algorithm for testing goal-minimality of graphs
An undirected graph G G with diameter k k is said to be goal-minimally k k -diametric if for every edge uv u v of G G the distance dG?uv(x,y)>k d G ? u v ( x , y ) > k if and only if {x,y}={u,v} { x , y } = { u , v } . We describe an efficient algorithm for determining whether a given graph is goal-minimally k k -diametric or not. In addition, we illustrate the use of the algorithm on a large graph with diameter 26.
diameter distance graph algorithm edge-critical