✦ LIBER ✦

An algorithm for the decomposition of graphs into cliques

✍ Scribed by Xiang-Ying Su

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 340 KB
Volume: 20
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190200208

No coin nor oath required. For personal study only.

✦ Synopsis

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 the following theorem: For any graph G with n vertices, the edge set E(G) can be decomposed into cliques such that the sum of the orders of the cliques is at most ⌊n^2^/2⌋. In this paper, we give a polynomial algorithm for the decomposition of E(G) into cliques which satisfies the condition of the theorem. The time required for this algorithm is at most O(n^3^). The algorithm may be regarded as a support for Winkler's conjecture posed in P. Winkler (Problem 27, Discrete Math. 101 (1992), 359–360). © 1995, John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

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.

Decomposition algorithms for the maximum

Decomposition algorithms for the maximum-weight connected graph problem

✍ Heungsoon Felix Lee; Daniel R. Dooly 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 1 views

An Algorithm for the Modular Decompositi

An Algorithm for the Modular Decomposition of Hypergraphs

✍ Paola Bonizzoni; Gianluca Della Vedova 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 147 KB

We propose an O n algorithm to build the modular decomposition tree of hypergraphs of dimension three and show how this algorithm can be generalized to time the decomposition of hypergraphs of any fixed dimension k.

Sharp bounds for decompositions of graph

Sharp bounds for decompositions of graphs into completer-partite subgraphs

✍ Gregory, David A.; Vander Meulen, Kevin N. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 435 KB 👁 2 views

If G is a graph on n vertices and r 2 2, w e let m,(G) denote the minimum number of complete multipartite subgraphs, with r or fewer parts, needed to partition the edge set, f(G). In determining m,(G), w e may assume that no two vertices of G have the same neighbor set. For such reduced graphs G, w

On the decomposition of kn into complete

On the decomposition of kn into complete bipartite graphs

✍ H. Tverberg 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 76 KB 👁 1 views

## Abstract A short proof is given of the impossibility of decomposing the complete graph on __n__ vertices into __n__‐2 or fewer complete bipartite graphs.

An algorithm for finding factorizations

An algorithm for finding factorizations of complete graphs

✍ A. J. W. Hilton; Matthew Johnson 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 58 KB 👁 1 views

## Abstract We show how to find a decomposition of the edge set of the complete graph into regular factors where the degree and edge‐connectivity of each factor is prescribed. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 132–136, 2003