Smallest-last ordering and clustering and graph coloring algorithms

1983/07/01 by David W. Matula, Leland L. Beck · 533 citations
Decision Sciences · Computer Science · #Scheduling and Timetabling Solutions #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Citation #Cluster analysis #Algorithm #Computer science #Graph coloring #Graph #Library science #Artificial intelligence #Theoretical computer science

paper · pdf · doi:10.1145/2402.322385

published in Journal of the ACM 30(3), 417-427 (Association for Computing Machinery)

openalex publication_date 1983/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/19

Abstract

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.

Citations

• An inequality for the chromatic number of a graph
• New methods to color the vertices of a graph
• Reducibility among Combinatorial Problems

Cited by

• Greedy coloring [wikipedia]