๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Hard graphs for the maximum clique problem

โœ Scribed by Cornelis Hoede

Publisher
Elsevier Science
Year
1988
Tongue
English
Weight
299 KB
Volume
72
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

The maximum number of cliques in dense g
The maximum number of cliques in dense graphs
โœ Bruce Hedman ๐Ÿ“‚ Article ๐Ÿ“… 1985 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 372 KB

Denote the number of vertices of G by ]G[. A clique of graph G is a maximal complete subgraph. The density oJ(G) is the number of vertices in the largest clique of G. If ยขo(G)>~ยฝ ]GI, then G has at most 2 tยฐl-'cG) cliques. The extremal graphs are then examined as wen. ## Terminology We will be co

Efficient algorithms for finding maximum
Efficient algorithms for finding maximum cliques of an overlap graph
โœ Sumio Masuda; Kazuo Nakajima; Toshinobu Kashiwabara; Toshio Fujisawa ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 728 KB

Let F = { I , , 12,. . . , Z,,} be a finite family of closed intervals on the real line. Two intervals 4 and Ik in F are said to overlap each other if they intersect but neither one of them contains the other. A graph G = (V, E) is called an overlap graph for F if there is a one-to-one correspondenc

Algorithms for a maximum clique and a ma
Algorithms for a maximum clique and a maximum independent set of a circle graph
โœ F. Gavril ๐Ÿ“‚ Article ๐Ÿ“… 1973 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 523 KB

## Abstract Consider a family of chords in a circle. A circle graph is obtained by representing each chord by a vertex, two vertices being connected by an edge when the corresponding chords intersect. In this paper, we describe efficient algorithms for finding a maximum clique and a maximum indepen