Smallest-Last Ordering and Clustering and Graph Coloring Algorithms

Smallest-last vertex ordering and prlonty search are utdlzed to show for any graph G = (IT, E) that the set of all connected subgraphs maxunal with respect to their minimum degree can be determined in O(I EI + I VI) time and 21El + O(I VI) space It is further noted that

the smallest-last graph coloring algonthrn can be unplemented in O(I E I + I V[) tune, and particularly effective aspects of the resulting coloring are discussed. Categories and Subject Descriptors' E 2 [Data Storage Representations]: eomiguous representations, F 2 2 [Analysis of Algorithms and Problem Complexity]' Nonnumerical Algorithms and Problems; G 2.2 [Discrete Mathematics] Graph Theory--graph algorithms, H 3 3 [Information Storage and Re- trieval] Information Search and Retrieval--clustering General Terms Algorithms, Theory Additional Key Words and Phrases. Adjacency structure, duster analysis, degree structure, graph coloring, h~erarc~cal cluster analys~s, lmear-tlme algonthms, linkage clustering, priority search, smallest-last coloring, smallest-last ordenng 1. Introduction and Summary The vertices vl, v2 ..... vn of a graph are said to be in smallest-last order whenever v~ has minimum degree in the maximal subgraph on the vertices vl, v2 ..... v, for all i. Properties associated with a smallest-last order provide for substantive utilization in a variety of areas, which we illustrate with applications in cluster analysis and graph coloring. In Section 2 we show that a smallest-last vertex ordering for a graph with vertex set Vand edge set E can be determined in time O(IEI + I VI) requiring only O(I VI) additional space, given...

Website: www.dcs.gla.ac.uk | Filesize: -
No of Page(s): 11
Download Smallest-Last Ordering and Clustering and Graph Coloring Algorithms.pdf