1986/11/01 by Egon Balas, Chang Sung Yu · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Graph Labeling and Dimension Problems #Combinatorics #Induced subgraph isomorphism problem #Mathematics #Induced subgraph #Clique graph #Graph #Subgraph isomorphism problem #Clique #Upper and lower bounds #Discrete mathematics #Computational complexity theory #Degeneracy (biology) #Chromatic scale #Graph power #Algorithm #Line graph #Vertex (graph theory) #Voltage graph
paper · doi:10.1137/0215075
openalex publication_date 1986/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/20
We describe a new type of branch and bound procedure for finding a maximum clique in an arbitrary graph G = (V,E). The two main ingredients, both of O(|V| + |E|) time complexity, are (i) an algorithm for finding a maximal triangulated induced subgraph of G; and (ii) an algorithm for finding a maximal k-chromatic induced subgraph of G. We discuss computational experience on randomly generated graphs with up to 400 vertices and 30,000 edges.