Recognition
It is straightforward to verify that a given graph with n vertices and m edges is claw-free in time O(n4), by testing each 4-tuple of vertices to determine whether they induce a claw. Somewhat more efficiently, but more complicatedly, one can test whether a graph is claw-free by checking, for each vertex of the graph, that the complement graph of its neighbors does not contain a triangle. A graph contains a triangle if and only if the cube of its adjacency matrix contains a nonzero diagonal element, so finding a triangle may be performed in the same asymptotic time bound as n × n matrix multiplication. Therefore, using the Coppersmith–Winograd algorithm, the total time for this claw-free recognition algorithm would be O(n3.376).
Kloks, Kratsch & Müller (2000) observe that in any claw-free graph, each vertex has at most 2√m neighbors; for otherwise by Turán's theorem the neighbors of the vertex would not have enough remaining edges to form the complement of a triangle-free graph. This observation allows the check of each neighborhood in the fast matrix multiplication based algorithm outlined above to be performed in the same asymptotic time bound as 2√m × 2√m matrix multiplication, or faster for vertices with even lower degrees. The worst case for this algorithm occurs when Ω(√m) vertices have Ω(√m) neighbors each, and the remaining vertices have few neighbors, so its total time is O(m3.376/2) = O(m1.688).
Read more about this topic: Claw-free Graph
Famous quotes containing the word recognition:
“By now, legions of tireless essayists and op-ed columnists have dressed feminists down for making such a fuss about entering the professions and earning equal pay that everyones attention has been distracted from the important contributions of mothers working at home. This judgment presumes, of course, that prior to the resurgence of feminism in the 70s, housewives and mothers enjoyed wide recognition and honor. This was not exactly the case.”
—Mary Kay Blakely (20th century)
“No democracy can long survive which does not accept as fundamental to its very existence the recognition of the rights of minorities.”
—Franklin D. Roosevelt (18821945)
“The recognition of Russia on November 16, 1933, started forces which were to have considerable influence in the attempt to collectivize the United States.”
—Herbert Hoover (18741964)