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

Finding maximum cliques in circle graphs

โœ Scribed by D. Rotem; J. Urrutia

Publisher
John Wiley and Sons
Year
1981
Tongue
English
Weight
505 KB
Volume
11
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

โœฆ Synopsis

Abstract

A circle diagram consists of a circle C and a set of n chords. This diagram defines a graph with n vertices where each vertex corresponds to a chord, and two vertices are adjacent if their corresponding chords intersect in C. A graph G is called a circle graph if it is defined by some circle diagram. An algorithm which requires O(n^2^) steps to generate one maximum clique is presented. The algorithm can also be used to generate all maximum cliques where the number of steps need to generate each additional maximum clique is linear in its size. This compares favourably with Gavril's algorithm [4] which works in O(n^3^) steps.

๐Ÿ“œ SIMILAR VOLUMES

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

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

Finding dominating cliques efficiently,
Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
โœ Dieter Kratsch ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 914 KB

We study a new version of the domination problem in which the dominating set is required to be a clique. The minimum dominating clique problem is NP-complete for split graphs and, hence, for chordal graphs. We show that for two other important subclasses of chordal graphs the problem is solvable eff