Decomposition by clique separators

Research output: Contribution to journalArticle

273 Scopus citations

Abstract

We consider the problem of decomposing a graph by means of clique separators, by which we mean finding cliques (complete graphs) whose removal disconnects the graph. We give an O(nm)-time algorithm for finding a decomposition of an n-vertex, m-edge graph. We describe how such a decomposition can be used in divide-and-conquer algorithms for various graph problems, such as graph coloring and finding maximum independent sets. We survey classes of graphs for which such divide-and-conquer algorithms are especially useful.

Original languageEnglish (US)
Pages (from-to)221-232
Number of pages12
JournalDiscrete Mathematics
Volume55
Issue number2
DOIs
StatePublished - Jul 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Decomposition by clique separators'. Together they form a unique fingerprint.

  • Cite this