### 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 language | English (US) |
---|---|

Pages (from-to) | 221-232 |

Number of pages | 12 |

Journal | Discrete Mathematics |

Volume | 55 |

Issue number | 2 |

DOIs | |

State | Published - Jul 1985 |

Externally published | Yes |

### 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

Tarjan, R. E. (1985). Decomposition by clique separators.

*Discrete Mathematics*,*55*(2), 221-232. https://doi.org/10.1016/0012-365X(85)90051-2