✦ LIBER ✦

Decomposition by clique separators

✍ Scribed by Robert E. Tarjan

Publisher: Elsevier Science
Year: 1985
Tongue: English
Weight: 751 KB
Volume: 55
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(85)90051-2

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Clique-sums, tree-decompositions and com

Clique-sums, tree-decompositions and compactness

✍ Igor Kříž; Robin Thomas 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 588 KB

## We develop a technique for extending excluded minor theorems to infinite graphs, and in particular we answer a question of Neil Robertson.

Algorithms on clique separable graphs

✍ Fǎnicǎ Gavril 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 925 KB

We define a family of graphs. tailed the clique sepambk graphs. characterized by the fact that they have completely connected rut sets by which we decompose them into r)arts such that when no further decomposition is possible we have a set of simple subgraphs. For example the chordal gmphs and the i

The greedy clique decomposition of a gra

The greedy clique decomposition of a graph

✍ Sean McGuinness 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 181 KB

## Abstract We prove that if maximal cliques are removed one by one from any graph with __n__ vertices, then the graph will be empty after at most __n__^2^/4 steps. This proves a conjecture of Winkler.

A note on a conjecture by Gavril on cliq

A note on a conjecture by Gavril on clique separable graphs

✍ D.G. Corneil; J.M. Keil 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 193 KB

conjecture concerning the characterization of clique

An algorithm for the decomposition of gr

An algorithm for the decomposition of graphs into cliques

✍ Xiang-Ying Su 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 340 KB 👁 1 views

## Abstract Chung (F. R. K. Chung, On the decomposition of graphs, __SIAM J. Algebraic Discrete Methods__ 23 (1981), 1–12.) and independently Györi and Kostochka (E. Györi and A. V. Kostochka, On a problem of G. O. H. Katona and T. Tarján, __Acta Math. Acad. Sci. Hung.__ 34 (1979), 321–327.) proved

Clique partitions and clique coverings

✍ Paul Erd'́os; Ralph Faudree; Edward T. Ordman 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 575 KB

Several new tools are presented for determining the number of cliques needed to (edge-)partition a graph. For a graph on n vertices, the clique partition number can grow et-? times as fast as the clique covering number, where c is at least l/64. If in a clique on n vertices, the edges between cn" ve